Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs

zbMATH Open1296.05115arXiv1301.1512MaRDI QIDQ2875486FDOQ2875486

Authors: Bo Ning 

Publication date: 15 August 2014

Published in: The Australasian Journal of Combinatorics (Search for Journal in Brave)

Abstract: A graph $G$ on $n$ vertices is Hamiltonian if it contains a spanning cycle, and pancyclic if it contains cycles of all lengths from 3 to $n$. In 1984, Fan presented a degree condition involving every pair of vertices at distance two for a 2-connected graph to be Hamiltonian. Motivated by Fan's result, we say that an induced subgraph $H$ of $G$ is $f_1$-heavy if for every pair of vertices $u,vinV(H)$, $d_H(u,v)=2$ implies $maxd(u),d(v)geq(n+1)/2$. For a given graph $R$, $G$ is called $R$-$f_1$-heavy if every induced subgraph of $G$ isomorphic to $R$ is $f_1$-heavy. In this paper we show that for a connected graph $S$ with $Seq{P}_3$ and a 2-connected claw-$f_1$-heavy graph $G$ which is not a cycle, $G$ being $S$-$f_1$-heavy implies $G$ is pancyclic if $S=P_4,Z_1$ or $Z_2$, where claw is $K_{1,3}$ and $Z_i$ is the path $a_1{a}_2{a}_3\mathrm{...}{a}_{i+2}{a}_{i+3}$ plus the edge $a_1{a}_3$. Our result partially improves a previous theorem due to Bedrossian on pancyclicity of 2-connected graphs.

Full work available at URL: https://arxiv.org/abs/1301.1512

Recommendations

• A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs
• A Fan-type heavy triple of subgraphs for pancyclicity of 2-connected graphs
• Hamilton cycles in claw-heavy graphs with Fan-type condition restricted to two induced subgraphs.
• Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity
• Clique-heavy subgraphs and pancyclicity of 2-connected graphs

zbMATH Keywords

Hamiltonian cycleHamiltonian graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Cited In (6)

• Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs
• Fan's condition on induced subgraphs for circumference and pancyclicity
• Clique-heavy subgraphs and pancyclicity of 2-connected graphs
• A triple of heavy subgraphs ensuring pancyclicity of 2-connected graphs
• A Fan-type heavy triple of subgraphs for pancyclicity of 2-connected graphs
• A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs

This page was built for publication: Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875486)