Opuscula Mathematica
Opuscula Math. 37, no. 4 (2017), 617-639

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)
References ▼
  1. [1] P. Bedrossian, Forbidden subgraph and minimum degree conditions for Hamiltonicity, Ph. D. Thesis, Memphis State University, USA (1991).
  2. [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. [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. [4] J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (1971), 121-132.
  5. [5] J.A. Bondy, Pancyclic graphs, J. Combin. Theory Ser. B 11 (1971), 80-84.
  6. [6] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, London, 2008.
  7. [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. [8] G. Chen, B. Wei, X. Zhang, Degree-light-free graphs and Hamiltonian cycles, Graphs Combin. 17 (2001), 409-434.
  9. [9] G. Chen, B. Wei, X. Zhang, Forbidden graphs and Hamiltonian cycles, preprint (1995).
  10. [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. [11] G.-H. Fan, New Sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), 221-227.
  12. [12] R. Faudree, R. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997), 45-60.
  13. [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. [14] S. Goodman, S.T. Hedetniemi, Sufficient conditions for a graph to be hamiltonian, J. Combin. Theory Ser. B 16 (1974), 175-180.
  15. [15] R.J. Gould, M.S. Jacobson, Forbidden subgraphs and Hamiltonian properties of graphs, Discrete Math. 42 (1982), 189-196.
  16. [16] R. Han, Another cycle structure theorem for hamiltonian graphs, Discrete Math. 199 (1999), 237-243.
  17. [17] G. Li, B. Wei, T. Gao, A structural method for hamiltonian graphs, Australas. J. Combin. 11 (1995), 257-262.
  18. [18] B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014), 127-136.
  19. [19] B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013), 1715-1725.
  20. [20] E.F. Schmeichel, S.L. Hakimi, A cycle structure theorem for Hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988), 99-107.
  21. [21] W. Wideł, A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs, Disc. Math. Graph Theory 36 (2016), 173-184.
About the authors ▼
Wojciech Wideł
AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
About the article ▼
Communicated by Ingo Schiermeyer.
Received: 2016-07-03.
Revised: 2016-11-23.
Accepted: 2016-11-23.
Published online: 2017-04-28.
Cite this article as ▼
Wojciech Wideł, Fan's condition on induced subgraphs for circumference and pancyclicity, Opuscula Math. 37, no. 4 (2017), 617-639, http://dx.doi.org/10.7494/OpMath.2017.37.4.617.
Download this article's citation as: