The hamiltonicity and pancyclicity of split graphs

Document Type : Original paper

Authors

1 School of Mathematical Science, Tianjin Normal University, Tianjin 300387, China

2 Institute of Mathematics and Interdisciplinary Sciences, Tianjin Normal University, Tianjin 300387, China

3 Laboratoire Interdisciplinaire des Sciences du Num´erique, UMR9015 CNRS and Universit´e Paris-Saclay, Campus Universitaire, Orsay 91405, France

Abstract

A split graph is a graph whose vertex set can be partitioned into two disjoint subsets (either of which may be empty) such that one subset induces a clique and the other induces an independent set. Regarding the hamiltonicity of such graphs, Dai et al. [Discrete Math. 345 (2022), 112826] conjectured that every $r$-connected $K_{1, r+1}$-free split graph is hamiltonian. In this paper, we provide a partial verification of this conjecture for the case $r=4$. Precisely, we show that every $4$-connected $\{K_{1,5}, K_{1,5}+e\}$-free split graph is hamiltonian.
        
Furthermore, we address Bondy’s meta-conjecture proposed in 1971, which asserts that almost any nontrivial condition guaranteeing a graph to be hamiltonian also implies the graph to be pancyclic, except for a small number of well-characterized exceptional graphs. We prove that this meta-conjecture holds for split graphs.

Keywords

Main Subjects

References

[1] R.E.L. Aldred, Y. Egawa, J. Fujisawa, K. Ota, and A. Saito, The existence of a 2-factor in K1,n-free graphs with large connectivity and large edge-connectivity, J. Graph Theory 68 (2011), no. 1, 77–89. https://doi.org/10.1002/jgt.20541
[2] R.E.L. Aldred, J. Fujisawa, and A. Saito, Forbidden subgraphs and the existence of a 2-factor, J. Graph Theory 64 (2010), no. 3, 250–266. https://doi.org/10.1002/jgt.20454
[3] , Pairs and triples of forbidden subgraphs and the existence of a 2-factor, J. Graph Theory 90 (2019), no. 1, 61–82.
https://doi.org/10.1002/jgt.22368
[4] P. Bedrossian, Forbidden subgraph and minimum degree conditions for hamiltonicity, Ph.D. thesis, Memphis State University, 3720 Alumni Ave, Memphis, TN 38152, United States.
[5] A. Benhocine and A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graph, J. Combin. Theory Ser. B 42 (1987), 167–180.
[6] J.A. Bondy, Pancyclic graphs, I, J. Combin. Theory Ser. B 11 (1971), no. 1, 80–84. https://doi.org/10.1016/0095-8956(71)90016-5
[7] J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008.
[8] G. Dai, Z.B. Zhang, H. Broersma, and X. Zhang, The hamiltonian properties in $K_{1,r}$-free split graphs, Discrete Math. 345 (2022), no. 6, 112826. https://doi.org/10.1016/j.disc.2022.112826
[9] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. 3 (1952), no. 1, 69–81. https://doi.org/10.1112/plms/s3-2.1.69
[10] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997), no. 1-3, 45–60. https://doi.org/10.1016/S0012-365X(96)00147-1
[11] S. Foldes and P.L. Hammer, Split graphs, Proceeding of the 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing, vol. 29, 1977, pp. 311–315.
[12] R.J. Gould, Advances on the hamiltonian problem–A survey, Graphs Combin. 19 (2003), 7–52. https://doi.org/10.1007/s00373-002-0492-x
[13] P. Holub, Z. Ryjáček, P. Vrána, S. Wang, and L. Xiong, Forbidden pairs of disconnected graphs for 2-factor of connected graphs, Graphs Combin. 100 (2022), no. 2, 209–231.
https://doi.org/10.1002/jgt.22773
[14] K.I. Kawarabayashi, A survey on hamiltonian cycles, Interdiscip. Inform. Sci. 7 (2001), no. 1, 25–39.
https://doi.org/10.4036/iis.2001.25
[15] B. Li and P. Vrána, Forbidden pairs of disconnected graphs implying hamiltonicity, J. Graph Theory 84 (2017), no. 3, 249–261. https://doi.org/10.1002/jgt.22024
[16] H. Li, Generalizations of Dirac’s theorem in hamiltonian graph theory—A survey, Discrete Math. 313 (2013), no. 19, 2034–2053. https://doi.org/10.1016/j.disc.2012.11.025
[17] H. Li, J. Cai, and W. Ning, An implicit degree condition for pancyclicity of graphs, Graphs Combin. 29 (2013), 1459–1469. https://doi.org/10.1007/s00373-012-1198-3
[18] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984), no. 1, 139–146.
https://doi.org/10.1002/jgt.3190080116
[19] J. Moon and M. Moser, On hamiltonian bipartite graphs, Israel J. Math. 1 (1963), 163–165. https://doi.org/10.1007/BF02759704
[20] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960), 55. https://doi.org/10.2307/2308928
[21] P. Renjith and N. Sadagopan, The hamiltonian cycle in K1,r-free split graphs—A dichotomy, Internat. J. Found. Comput. Sci. 33 (2022), no. 1, 1–32. https://doi.org/10.1142/S0129054121500337
[22] E.F. Schmeichel and S.L. Hakimi, Pancyclic graphs and a conjecture of Bondy and Chav´atal, J. Combin. Theory Ser. B 17 (1974), no. 1, 22–34. https://doi.org/10.1016/0095-8956(74)90043-4
[23] E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988), no. 1, 99–107. https://doi.org/10.1016/0095-8956(88)90058-5
Communications in Combinatorics and Optimization
Volume 11, Issue 4
Special issue in honor of Prof. Odile Favaron
December 2026
Pages 1305-1317

Files

Share

How to cite

Statistics