几类特殊邻域图的刻画

Characterizations of Some Special Neighborhood Graphs

几类特殊邻域图的刻画.

Characterizations of Some Special Neighborhood-Graphs令G是一个顶点集为V(G),边集为E(G)的连通简单图。如果存在图G使得对于每个顶点v€V(G),满足G[N(v)] ≌ H,则称图H是可实现的。一个连通图G被称为Pk-邻域图,如果对于∀v ∈V(G),使得 G[N(v)]同构于Pk。本文首先分别给出了对任意的υ€V(G),满足G[N(v)]同构于P2或P3和P2及或K1,3的图G的刻画;其次,证明了图Km,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 Pk-neighborhood graph, if for ∀v ∈V(G) such that G[N(v)]≌ Pk. In this paper, we first give the characterizations of graphs such that ∀v ∈V(G) such that G[N(v)]≌P2, P3 or G[N(v)]≌P2,K1,3, respectively;Secondly,we prove that Km,n,(m≠n) are not realizable, and also prove that ∀v ∈V(G) suchthat , 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.