Operations Research Transactions

Previous Articles     Next Articles

The Hamilton-connectivity with the degree sum of  non-adjacent subgraphs P_ 4 and K_1 in claw-free graphs

ZHENG Wei1  WANG Ligong1,*   

  1. 1. Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an 710072, China
  • Received:2015-01-19 Online:2016-03-15 Published:2016-03-15

Abstract:

This paper studies the relationship between the degree of subgraphs and Hamiltonicity of graphs. It is proven that every 3-connected claw-free graph $G$ of order $n$ with minimum degree $\delta(G)\geq4$ is Hamilton-connected if it satisfies $d(H_1)+d(H_2)\geq n$ for any two non-adjacent subgraphs $H_1$, $H_2$ which are isomorphic to $P_4$, $K_1$ respectively.

Key words:  claw-free graph, non-adjacent subgraph, degree of subgraph, Hamilton-connected