آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 131 |
| تعداد مقالات | 1,634 |
| تعداد مشاهده مقاله | 1,899,064 |
| تعداد دریافت فایل اصل مقاله | 1,758,846 |
The hamiltonicity and pancyclicity of split graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 19، دوره 11، شماره 4، اسفند 2026، صفحه 1305-1317 اصل مقاله (2.41 M) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31342.2822 | ||
| نویسندگان | ||
| Junqing Cai1، 2؛ Hao Li* 3؛ Zhiyi Jiang1 | ||
| 1School of Mathematical Science, Tianjin Normal University, Tianjin 300387, China | ||
| 2Institute of Mathematics and Interdisciplinary Sciences, Tianjin Normal University, Tianjin 300387, China | ||
| 3Laboratoire Interdisciplinaire des Sciences du Num´erique, UMR9015 CNRS and Universit´e Paris-Saclay, Campus Universitaire, Orsay 91405, France | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| hamiltonian, pancyclic, split graph,؛ {K_(1؛ 5)؛ K_(1؛ 5) + e}-free graphs | ||
| مراجع | ||
|
[1] R.E.L. Aldred, Y. Egawa, J. Fujisawa, K. Ota, and A. Saito, The existence of a 2-factor in $K_{1,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] R.E.L. Aldred, J. Fujisawa, and A. Saito, 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 $K_{1,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 $K_{1,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átal, 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 | ||
|
آمار تعداد مشاهده مقاله: 353 تعداد دریافت فایل اصل مقاله: 330 |
||