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

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,v\in V(H)$, $d_H(u,v)=2$ implies $\max \{d(u),d(v)\}\ge (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 $S\ne 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...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.

11 pages; 2 figures; accepted by Australasian J. Combin