关于Faudree－Schelp定理的改进

一个图Ｃ＝（Ｖ，Ｅ）是［ｌ，ｍ］－泛连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为Ｋ—１的路Ｐｋ（ｘ，ｙ），Ｋ＝ｌ，ｌ＋ｌ，…，ｍ。Ｇ具有性质Ｐ（Ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥Ｋ。作者探讨了一类产（Ｋ）图的路连通性，改进了Ｆａｕｄｒｅｅ－Ｓｃｈｅｌｐ定理，得到两个定理：定理１设Ｇ＝（Ｖ，Ｅ）是ｎ阶Ｐ（ｎ—１）图。如果Ｇ是［ｎ—１，ｎ］－泛连通的，则Ｇ是［８，ｎ］－泛连通图（ｎ≥８）．定理２设Ｇ是３－连通ｎ阶Ｐ（ｎ）图。如果Ｇ的独立数α（Ｇ）＜ｎ／２，则Ｇ是［５，ｎ］－泛连通图，ｎ≥５．

AN IMPROVEMENT OF FAUDREE-SCHELP THEOREM ON PATH-CONNECTED GRAPHS

A graph G=(V,E)is called P(K)-graph if d(x) d(y)>K holds for every twovenices x and y in v with distance 2. G is 1],m]-panconnected if for every two venices ofG,there is a K-vertex path connecting them, where K=1, 1 1, 1 2, ...,m.In this paper,we study the path-connectivety of a kind of P(K)-graph and make animprovement of Faudree Schelp Theorem on path--connected graphs as follows.