Opuscula Math. 37, no. 4 (2017), 617-639
http://dx.doi.org/10.7494/OpMath.2017.37.4.617

Opuscula Mathematica

# Fan's condition on induced subgraphs for circumference and pancyclicity

Wojciech Wideł

Abstract. Let $$\mathcal{H}$$ be a family of simple graphs and $$k$$ be a positive integer. We say that a graph $$G$$ of order $$n\geq k$$ satisfies Fan's condition with respect to $$\mathcal{H}$$ with constant $$k$$, if for every induced subgraph $$H$$ of $$G$$ isomorphic to any of the graphs from $$\mathcal{H}$$ the following holds: $\forall u,v\in V(H)\colon d_H(u,v)=2\,\Rightarrow \max\{d_G(u),d_G(v)\}\geq k/2.$ If $$G$$ satisfies the above condition, we write $$G\in\mathcal{F}(\mathcal{H},k)$$. In this paper we show that if $$G$$ is $$2$$-connected and $$G\in\mathcal{F}(\{K_{1,3},P_4\},k)$$, then $$G$$ contains a cycle of length at least $$k$$, and that if $$G\in\mathcal{F}(\{K_{1,3},P_4\},n)$$, then $$G$$ is pancyclic with some exceptions. As corollaries we obtain the previous results by Fan, Benhocine and Wojda, and Ning.

Keywords: Fan's condition, circumference, hamiltonian cycle, pancyclicity.

Mathematics Subject Classification: 05C38, 05C45.

Full text (pdf)

1. P. Bedrossian, Forbidden subgraph and minimum degree conditions for Hamiltonicity, Ph. D. Thesis, Memphis State University, USA (1991).
2. P. Bedrossian, G. Chen, R.H. Schelp, A generalization of Fan's condition for Hamiltonicity, pancyclicity and Hamiltonian connectedness, Discrete Math. 115 (1993), 39-50.
3. A. Benhocine, A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs, J. Combin. Theory Ser. B 42 (1987), 167-180.
4. J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (1971), 121-132.
5. J.A. Bondy, Pancyclic graphs, J. Combin. Theory Ser. B 11 (1971), 80-84.
6. J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, London, 2008.
7. H.J. Broersma, H.J. Veldman, Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of K1,3-free graphs, [in:] Contemporary Methods in Graph Theory, BI Wissenschaftsverlag, Mannheim, 1990, 181-194.
8. G. Chen, B. Wei, X. Zhang, Degree-light-free graphs and Hamiltonian cycles, Graphs Combin. 17 (2001), 409-434.
9. G. Chen, B. Wei, X. Zhang, Forbidden graphs and Hamiltonian cycles, preprint (1995).
10. D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, Proceedings of the 1980 International Conference on Graph Theory (1980), 297-316.
11. G.-H. Fan, New Sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), 221-227.
12. R. Faudree, R. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997), 45-60.
13. M. Ferrara, M.S. Jacobson, A. Harris, Cycle lengths in Hamiltonian graphs with a pair of vertices having large degree sum, Graphs Combin. 26 (2010), 215-223.
14. S. Goodman, S.T. Hedetniemi, Sufficient conditions for a graph to be hamiltonian, J. Combin. Theory Ser. B 16 (1974), 175-180.
15. R.J. Gould, M.S. Jacobson, Forbidden subgraphs and Hamiltonian properties of graphs, Discrete Math. 42 (1982), 189-196.
16. R. Han, Another cycle structure theorem for hamiltonian graphs, Discrete Math. 199 (1999), 237-243.
17. G. Li, B. Wei, T. Gao, A structural method for hamiltonian graphs, Australas. J. Combin. 11 (1995), 257-262.
18. B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014), 127-136.
19. B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013), 1715-1725.
20. E.F. Schmeichel, S.L. Hakimi, A cycle structure theorem for Hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988), 99-107.
21. W. Wideł, A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs, Disc. Math. Graph Theory 36 (2016), 173-184.
• Wojciech Wideł
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Communicated by Ingo Schiermeyer.
• Revised: 2016-11-23.
• Accepted: 2016-11-23.
• Published online: 2017-04-28.