The Hamilton-Connectivity with the Degree Sum of Non-adjacent Subgraphs of Claw-free Graphs  

作　　者：Wei ZHENG Li-gong WANG 

机构地区：[1]Department of Applied Mat hem a tics,School of Science,Northwes tern Polytechnical Univers计y,Xi5an 710072,China [2]Xi'an-Budapest Joint Research Center for Combinatorics,Northwestern Polytechnical University,Xi'an 710129,China

出　　处：《Acta Mathematicae Applicatae Sinica》2019年第3期580-590,共11页应用数学学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.11871398);the Natural Science Basic Research Plan in Shaanxi Province of China(Program No.2018JM1032);the Fundamental Research Funds for the Central Universities(No.3102019ghjd003);the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical University(No.ZZ2019031)

摘　　要：The degree d(H)of a subgraph H of a graph G is|u∈∪V(H)N(u)-V(H)|,where N(u)denotes the neighbor set of the vertex u of G.In this paper,we prove the following result on the condition of the degrees of subgraphs.Let G be a 2-connected claw-free graph of order n with minimum degreeδ(G)≥3.If for any three non-adjacent subgraphs H1,H2,H3 that are isomorphic to K1,K1,K2,respectively,there is d(H1)+d(H2)+d(H3)≥n+3,then for each pair of vertices u,v∈G that is not a cut set,there exists a Hamilton path between u and v.The degree d（H） of a subgraph H of a graph G is ■, where N（u） denotes the neighbor set of the vertex u of G. In this paper, we prove the following result on the condition of the degrees of subgraphs. Let G be a 2-connected claw-free graph of order n with minimum degree δ（G）≥3. If for any three non-adjacent subgraphs H1, H2, H3 that are isomorphic to K1, K1, K2, respectively, there is d（H1） + d（H2） + d（H3）≥n + 3, then for each pair of vertices u, v∈G that is not a cut set, there exists a Hamilton path between u and v.

关 键 词：CLAW-FREE graph non-adjacent SUBGRAPH degree of SUBGRAPH Hamilton path 

分 类 号：O1[理学—数学]