期刊文献+

关于Faudree-Schelp定理的改进

An Improvement of Faudree-Schelp Theorem on Path-Connected Graphs
下载PDF
导出
摘要 一个图G=(V,E)是[l,m]-路连通的,如果在G的任意一对节点x与y之间有长为k-1的路Pk(x,x),k=l,l+1,…,m.G具有性质P(k),如果对G的任何一对距离为2的节点x和y,有d(x)+d(y)≥k.本文作者探讨了一类P(k)图的路连通性,改进了Faudree-Schelp定理,得到了以下的定理1设G=(V,E)是n阶P(n—1)图.如果G是[n-1,n]-路连通的,则G是[8,n]-路连通图(n≥8).定理2设G=(V,E)是n阶3-连通P(n)图(n≥5).如果G的独立数α(G)<n/2,则G是[5,n]-路连通图. 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).
作者 任韩
出处 《新疆大学学报(自然科学版)》 CAS 1995年第1期17-27,共11页 Journal of Xinjiang University(Natural Science Edition)
关键词 路连通图 P(k)-图 F-S定理 Path-connected graphs p(k)-graped
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部