关于Faudree－Schelp定理的改进

An Improvement of Faudree-Schelp Theorem on Path-Connected Graphs

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

A graph G in [l,m]-Path --connected if for every two venices of G,there is a k-vertex path connecting them, where k=l,l + 1, …, m. G is named P (k)-graph if d (x) + d (y) ≥k holds for every pairs of venices x and y of G with distance 2.In this paper we study the path-connectivity of a kind of p(k) -graph and make an improvement of Faudree-Schelp Theorem on path-connected graphs.Theorem 1. Let G= (V,E) be an n-vertex p(n -1)-graph. If G is [n-1,n]-path-connected, then G is [8,n]-path-connected (n≥8).Theorem 2. Let G= (V,E) be a 3-connected p(n)-graph n venices. If the independent number a(G)<n/2,then G is [5,n]-path-connected (n≥5).