一类满足α(H)=4的非树图

AN INFINITE CLASS OF GRAPHS WITH a(H)=4 THAT ARE NOT TREES

用C(H)表示图H的中心,”■”表示图同构,定义图参数文[2]和[3]构作了某些满足α=3的图,解决了α=3的图的存在问题,本文构作了一类满足α=4的图,解决了α=4的非树图的存在问题。令n和m都是自然数。设H是一个图,d(H)=d_H(x_1,x_2)=2m-1.H=(∨(H),E(H)),其中定理令n>m.若H满足A.(?)u∈∨(H),有d_H(u,x_1)+d_H(u,x_2)≤2m;B.存在v_0∈(H),使d_H(v_0,x_1)+d_H(v_0,x_1)=2m;C.不存在v∈(H),使d_H(v,x_1)=d_H(v,x_2)=m。则α(H)=4。

For every graph H we define a(H)=min{~ V(G)^-V(H)~:C(G)≌H}.Clearly, the graphs with a=0 are what usually called self-centered graphs. For non-self-centered graphs, F. Buddy、 Z. Miller and P. J. Slaler [1] mention that: a(H)≤4 and a(H)≠1 for every graph H, and show that there do not exsist any tree with a=3. They also completely characterize the classes of trees with a = 2, 4. Chen Zhibai [2] and Liu Xiangwu [3] construct some classes of graphs with a=3. The author [4] points out some characters of supergraphs of graphs with a=3. Up to now, nobody discusses the graphs with a=4 that are not trees.In this paper we construct an infinite class of graphs with a = 4 that are not trees.