2012/09/18 by Bo Ning, Bing Chen, Ning, Bo +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1209.3899
Withdraw this preprint since the results will be added to arxiv:1212.6466
openalex publication_date 2012/09/18 · arxiv created 2013/01/04 · arxiv updated 2013/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on n≥ 3 vertices, claw the bipartite graph K1,3, and Zi the graph obtained from a triangle by attaching a path of length i to its one vertex. G is called 1-heavy if at least one end vertex of each induced claw of G has degree at least n/2, and claw-o-heavy if each induced claw of it has a pair of end vertices with degree sum at least n. In this paper we prove two results: (1) Every 2-connected claw-o-heavy graph G is Hamiltonian if every pair of vertices u,v in a subgraph H≅ Z1 contained in an induced subgraph Z2 of G with dH(u,v)=2 satisfies one of the following conditions: (a) |N(u)∩ N(v)|≥ 2; (b) max(d(u),d(v))≥ n/2. (2) Every 3-connected 1-heavy graph G is Hamiltonian if every pair of vertices u,v in an induced subgraph H≅ Z2 of G with dH(u,v)=2 satisfies one of the following conditions: (a) |N(u)∩ N(v)|≥ 2; (b) max(d(u),d(v))≥ n/2. Our results improve or extend previous theorems of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson and Shi on the existence of Hamilton cycles in graphs.