Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs
classification
🧮 math.CO
keywords
heavygraphsconnectedeverymathcalsubgraphverticescalled
read the original abstract
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 $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$-heavy if $G$ is $H$-heavy for every $H\in\mathcal{H}$. In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.