[Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.
[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.
[Li, Hao] Univ Paris Sud, LRI, UMR CNRS UPS 8623, F-91405 Orsay, France.
通讯机构：
[Chen, Guantao] G
Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.
语种：
英文
关键词：
Cycle;Path;Degree;Toughness;Connectivity
期刊：
Discrete Mathematics
ISSN：
0012-365X
年：
2012
卷：
312
期：
17
页码：
2584-2592
会议名称：
8th French Combinatorial Conference (FCC)
会议时间：
JUN 28-JUL 02, 2010
会议地点：
Orsay, FRANCE
会议主办单位：
[Chen, Guantao] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA.^[Hu, Zhiquan] Cent China Normal Univ, Fac Math & Stat, Wuhan 430079, Peoples R China.^[Li, Hao] Univ Paris Sud, LRI, UMR CNRS UPS 8623, F-91405 Orsay, France.
会议赞助商：
Algorithms Res Grp, Univ Paris-Sud 11, LRI, Graph Theory & Combinatorial Optimizat Res Grp, CNRS, French Minist Educ, GDR/CNRS-IM, Lab Comp Sci (LRI), Univ Paris-Sud 11
The second author was financially supported by the NSFC grant 11071096 and by self-determined research funds of CCNU09Y01005 and CCNU09Y01018 from the colleges’ basic research and operation of MOE.
机构署名：
本校为其他机构
院系归属：
数学与统计学学院
摘要：
A path in a graph is called extendable if it is a proper subpath of another path. A graph is locally connected if every neighborhood induces a connected subgraph. We show that, for each graph G of order n, there exists a threshold number s such that every path of order smaller than s is extendable and there exists a non-extendable path of order t for each t is an element of {s, ... , n - 1} if G satisfies any one of the following three conditions: the degree sum d(u) + d(nu) >= n for any two nonadjacent vertices u and nu; P-4-free and omega(G - S)
