| Title:
|
Degree sums of adjacent vertices for traceability of claw-free graphs (English) |
| Author:
|
Tian, Tao |
| Author:
|
Xiong, Liming |
| Author:
|
Chen, Zhi-Hong |
| Author:
|
Wang, Shipeng |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
72 |
| Issue:
|
2 |
| Year:
|
2022 |
| Pages:
|
313-330 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The line graph of a graph $G$, denoted by $L(G)$, has $E(G)$ as its vertex set, where two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define $\bar {\sigma }_2 (H) = \min \{ d(u) + d(v) \colon uv \in E(H)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta (H)\geq 3$. We show that, if $\bar {\sigma }_2 (H) \geq \frac 17 (2n -5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček's closure ${\rm cl}(H)=L(G)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10 which have no spanning trail. Furthermore, if $\bar {\sigma }_2 (H) > \frac 13 (n-6)$ and $n$ is sufficiently large, then $H$ is traceable. The bound $\frac 13 (n-6)$ is sharp. As a byproduct, we prove that there are exactly eight graphs in the family ${\mathcal G}$ of 2-edge-connected simple graphs of order at most 11 that have no spanning trail, an improvement of the result in Z. Niu et al. (2012). (English) |
| Keyword:
|
traceable graph |
| Keyword:
|
line graph |
| Keyword:
|
spanning trail |
| Keyword:
|
closure |
| MSC:
|
05C07 |
| MSC:
|
05C38 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 07547206 |
| idMR:
|
MR4412761 |
| DOI:
|
10.21136/CMJ.2022.0544-19 |
| . |
| Date available:
|
2022-04-21T18:58:09Z |
| Last updated:
|
2024-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/150403 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244. Springer, New York (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5 |
| Reference:
|
[2] Brandt, S., Favaron, O., Ryjáček, Z.: Closure and stable Hamiltonian properties in claw-free graphs.J. Graph Theory 34 (2000), 30-41. Zbl 0946.05053, MR 1753065, 10.1002/(SICI)1097-0118(200005)34:1<30::AID-JGT4>3.0.CO;2-R |
| Reference:
|
[3] Brualdi, R. A., Shanny, R. F.: Hamiltonian line graphs.J. Graph Theory 5 (1981), 307-314. Zbl 0437.05041, MR 0625072, 10.1002/jgt.3190050312 |
| Reference:
|
[4] Catlin, P. A.: A reduction method to find spanning Eulerian subgraphs.J. Graph Theory 12 (1988), 29-44. Zbl 0659.05073, MR 0928734, 10.1002/jgt.3190120105 |
| Reference:
|
[5] Catlin, P. A., Han, Z.-Y., Lai, H.-J.: Graphs without spannning closed trails.Discrete Math. 160 (1996), 81-91. Zbl 0859.05060, MR 1417562, 10.1016/S0012-365X(95)00149-Q |
| Reference:
|
[6] Chen, Z.-H.: Hamiltonicity and degrees of adjacent vertices in claw-free graphs.J. Graph Theory 86 (2017), 193-212. Zbl 1370.05124, MR 3684782, 10.1002/jgt.22120 |
| Reference:
|
[7] Dirac, G. A.: Some theorems on abstract graphs.Proc. Lond. Math. Soc. (3) 2 (1952), 69-81. Zbl 0047.17001, MR 0047308, 10.1112/plms/s3-2.1.69 |
| Reference:
|
[8] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs: A survey.Discrete Math. 164 (1997), 87-147. Zbl 0879.05043, MR 1432221, 10.1016/S0012-365X(96)00045-3 |
| Reference:
|
[9] Gould, R. J.: Recent advances on the Hamiltonian problem: Survey III.Graphs Comb. 30 (2014), 1-46. Zbl 1292.05163, MR 3143857, 10.1007/s00373-013-1377-x |
| Reference:
|
[10] Li, D., Lai, H.-J., Zhan, M.: Eulerian subgraphs and Hamilton-connected line graphs.Discrete Appl. Math. 145 (2005), 422-428. Zbl 1057.05053, MR 2112533, 10.1016/j.dam.2004.04.005 |
| Reference:
|
[11] Matthews, M. M., Sumner, D. P.: Longest paths and cycles in $K_{1,3}$-free graphs.J. Graph Theory 9 (1985), 269-277. Zbl 0591.05041, MR 0797514, 10.1002/jgt.3190090208 |
| Reference:
|
[12] Niu, Z., Xiong, L., Zhang, S.: Smallest 2-edge-connected graphs without a spanning trail.Util. Math. 88 (2012), 381-397. Zbl 1256.05206, MR 2975848 |
| Reference:
|
[13] Ryjáček, Z.: On a closure concept in claw-free graphs.J. Comb. Theory, Ser. B 70 (1997), 217-224. Zbl 0872.05032, MR 1459867, 10.1006/jctb.1996.1732 |
| Reference:
|
[14] Shao, Y.: Claw-Free Graphs and Line Graphs: Ph.D Thesis.West Virginia University, Morgantown (2005). MR 2707853 |
| Reference:
|
[15] Singleton, J. E.: Maximal Nontraceable Graphs: Ph.D Thesis.University of South Africa, Pretoria (2006). MR 2717408 |
| Reference:
|
[16] Tian, T.: Degree Conditions for Hamiltonian Properties of Claw-free Graphs: Ph.D Thesis.University of Twente, Enschede (2018). |
| Reference:
|
[17] Tian, T., Broersma, H., Xiong, L.: On sufficient degree conditions for traceability of claw-free graphs.Discrete Math. 343 (2020), Article ID 111883, 10 pages. Zbl 1440.05163, MR 4073374, 10.1016/j.disc.2020.111883 |
| Reference:
|
[18] Tian, T., Xiong, L.: Traceability on 2-connected line graphs.Appl. Math. Comput. 321 (2018), 463-471. Zbl 07070099, MR 3732390, 10.1016/j.amc.2017.10.043 |
| Reference:
|
[19] Tian, T., Xiong, L.: 2-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices.Discuss. Math., Graph Theory 40 (2020), 85-106. Zbl 1439.05131, MR 4041969, 10.7151/dmgt.2125 |
| Reference:
|
[20] Veldman, H. J.: On dominating and spanning circuits in graphs.Discrete Math. 124 (1994), 229-239. Zbl 0789.05061, MR 1258856, 10.1016/0012-365X(92)00063-W |
| Reference:
|
[21] Wang, S., Xiong, L.: Spanning trails in a 2-connected graph.Electron. J. Comb. 26 (2019), Article ID P3.56, 19 pages. Zbl 1420.05089, MR 4017309, 10.37236/8121 |
| Reference:
|
[22] Xiong, L., Zong, M.: Traceability of line graphs.Discrete Math. 309 (2009), 3779-3785. Zbl 1218.05085, MR 2537372, 10.1016/j.disc.2008.10.012 |
| . |
