pith. machine review for the scientific record. sign in

arxiv: 1303.2263 · v4 · submitted 2013-03-09 · 🧮 math.CO

Recognition: unknown

Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity

Authors on Pith no claims yet
classification 🧮 math.CO
keywords heavyeverygraphinducedmathcalconditionconnecteddegree
0
0 comments X
read the original abstract

In 1984, Fan gave a sufficient condition involving maximum degree of every pair of vertices at distance two for a graph to be Hamiltonian. Motivated by Fan's result, we say that an induced subgraph $H$ of a graph $G$ is $f$-heavy if for every pair of vertices $u,v\in V(H)$, $d_{H}(u,v)=2$ implies that $\max\{d(u),d(v)\}\geq n/2$. For a given graph $R$, $G$ is called $R$-$f$-heavy if every induced subgraph of $G$ isomorphic to $R$ is $f$-heavy. For a family $\mathcal{R}$ of graphs, $G$ is $\mathcal{R}$-$f$-\emph{heavy} if $G$ is $R$-$f$-heavy for every $R\in \mathcal{R}$. In this note we show that every 2-connected graph $G$ has a Hamilton cycle if $G$ is $\{K_{1,3},P_7,D\}$-$f$-heavy or $\{K_{1,3},P_7,H\}$-$f$-heavy, where $D$ is the deer and $H$ is the hourglass. Our result is a common generalization of previous theorems of Broersma et al. and Fan on Hamiltonicity of 2-connected 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.