Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Abstract

Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on these induced subgraphs. Let $G$ be a graph on $n$ vertices and $H$ be an induced subgraph of $G$. $H$ is called \emph{o}-heavy if there are two nonadjacent vertices in $H$ with degree sum at least $n$, and is called $f$-heavy if for every two vertices $u,v\in V(H)$, $d_H(u,v)=2$ implies that $\max \{d(u),d(v)\}\ge n/2$. We say that $G$ is $H$-\emph{o}-heavy ($H$-\emph{f}-heavy) if every induced subgraph of $G$ isomorphic to $H$ is \emph{o}-heavy (\emph{f}-heavy). In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ such that every 2-connected $R$-\emph{f}-heavy and $S$-\emph{f}-heavy ($R$-\emph{o}-heavy and $S$-\emph{f}-heavy, $R$-\emph{f}-heavy and $S$-free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs.

21 pages, 2 figures

References in corpus (1)

• Heavy subgraph conditions for longest cycles to be heavy in graphs

Cited by in corpus (6)

• Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity
• Heavy subgraphs, stability and hamiltonicity
• Extremal problems on the Hamiltonicity of claw-free graphs
• Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
• Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs
• Degree conditions restricted to induced paths for hamiltonicity of claw-heavy graphs