2011/09/19 by Binlong Li, Zdeněk Ryjáček, Li, Binlong +5
Computer Science · Engineering · Mathematics · #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1109.4122
openalex publication_date 2011/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on n vertices. An induced subgraph H of G is called heavy if there exist two nonadjacent vertices in H with degree sum at least n in G. We say that G is H-heavy if every induced subgraph of G isomorphic to H is heavy. For a family H of graphs, G is called H-heavy if G is H-heavy for every H\inH. In this paper we characterize all connected graphs R and S other than P3 (the path on three vertices) such that every 2-connected \R,S\-heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian graphs.