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
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.
- P. Bedrossian, Forbidden subgraph and minimum degree conditions for Hamiltonicity, Ph. D. Thesis, Memphis State University, USA (1991).
- 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.
- 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.
- J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (1971), 121-132.
- J.A. Bondy, Pancyclic graphs, J. Combin. Theory Ser. B 11 (1971), 80-84.
- J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, London, 2008.
- 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.
- G. Chen, B. Wei, X. Zhang, Degree-light-free graphs and Hamiltonian cycles, Graphs Combin. 17 (2001), 409-434.
- G. Chen, B. Wei, X. Zhang, Forbidden graphs and Hamiltonian cycles, preprint (1995).
- 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.
- G.-H. Fan, New Sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), 221-227.
- R. Faudree, R. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997), 45-60.
- 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.
- S. Goodman, S.T. Hedetniemi, Sufficient conditions for a graph to be hamiltonian, J. Combin. Theory Ser. B 16 (1974), 175-180.
- R.J. Gould, M.S. Jacobson, Forbidden subgraphs and Hamiltonian properties of graphs, Discrete Math. 42 (1982), 189-196.
- R. Han, Another cycle structure theorem for hamiltonian graphs, Discrete Math. 199 (1999), 237-243.
- G. Li, B. Wei, T. Gao, A structural method for hamiltonian graphs, Australas. J. Combin. 11 (1995), 257-262.
- B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014), 127-136.
- B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013), 1715-1725.
- E.F. Schmeichel, S.L. Hakimi, A cycle structure theorem for Hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988), 99-107.
- 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.
- Received: 2016-07-03.
- Revised: 2016-11-23.
- Accepted: 2016-11-23.
- Published online: 2017-04-28.
