薄祥智, 孟吉翔. s-点连通图的路可扩性(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2010, 27(4): 405-407.DOI:
s-点连通图的路可扩性(英文)
摘要
设G是一个简单图.如果G的每一个有s个点的导出子图都连通
但存在一个s-1个点的导出子图不连通
则称G是s-点连通的
其中s≥3.一条路称为可扩的
如果存在路P′满足V(P′)V(P)且|V(P′)|=|V(P)|+1.一个图称为完全路可扩的
如果它的直径至多为2且它的每一条少于|V(G)|个顶点的路都是可扩的.本文证明了s-点连通图
如果它的顶点数n与s满足n≥2s-1
则它是完全路可扩的.
Abstract
Let G be a simple graph.G is called s-vertex connected if every induced subgraph with s vertices is connected but there exists an induced subgraph with s-1 vertices that is not connected
where s ≥ 3.A path P is extendable if there exists another path P′ such that V(P′)V(P) and |V(P′)|=|V(P)| + 1.A graph G is said to be fully path extendable if its diameter is at most two and every path P with |V(P)| < |V(G)| is extendable.In this paper
we prove that an s-vertex connected graph whose order is not less than 2s-1 is fully path extendable.
关键词
Keywords
references
Bondy J A,Murly U S R. Graph Theory with Application [M]. London: Macmillan Press Ltd,1796.
G. R.T. Hendry. Path extendable graphs [J]. Periodica Mathematica Hungarica,1998,21(3):205-219.
Wang Jianglu,Zhu yongjian. Path extendability of connected,locally 2-connected K 3 -free graphs[J]. Systems Sci Math Sci, 1997,10:267-274.