几类特殊邻域图的刻画

Characterizations of Some Special Neighborhood-Graphs

摘要: 几类特殊邻域图的刻画

Abstract: Characterizations of Some Special Neighborhood-Graphs 令G是一个顶点集为V(G)，边集为E(G)的连通简单图。如果存在图G使得对于每个顶点v€V(G)，满足G[N(v)] ≌ H，则称图H是可实现的。一个连通图G被称为P_k-邻域图，如果对于∀v ∈V(G),使得 G[N(v)]同构于P_k。本文首先分别给出了对任意的υ€V(G)，满足G[N(v)]同构于P₂或P₃和P₂及或K_1,3的图G的刻画;其次,证明了图K_m,n,(m≠n)是不可实现的; 此外,证明了对于任意的v∈V(G)，满足当且仅当图; 最后，给出了最大度为k且有一个顶点为2度点的不含3-太阳图的路-邻域图的刻画。 Let G be a simple connected graph with vertex set V (G) and edge set E(G). We call that graph H is realizable if there exists a graph G such that for each vertex v€V(G), G[N(v)] ≌ H. A connected graph G is called P_k-neighborhood graph, if for ∀v ∈V(G) such that G[N(v)]≌ P_k. In this paper, we first give the characterizations of graphs such that ∀v ∈V(G) such that G[N(v)]≌P₂, P₃ or G[N(v)]≌P₂,K_1,3, respectively; Secondly, we prove that K_m,n,(m≠n) are not realizable, and also prove that ∀v ∈V(G) such that , if and only if ; Finally, we give the characterization of 3-sun free path-neighborhood graph with maximum valency k and a vertex of degree two.