Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
traceable graph; line graph; spanning trail; closure
traceable graph; line graph; spanning trail; closure
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).
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, New York (2008). DOI 10.1007/978-1-84628-970-5 | MR 2368647 | Zbl 1134.05001
[2] Brandt, S., Favaron, O., Ryjáček, Z.: Closure and stable Hamiltonian properties in claw-free graphs. J. Graph Theory 34 (2000), 30-41. DOI 10.1002/(SICI)1097-0118(200005)34:1<30::AID-JGT4>3.0.CO;2-R | MR 1753065 | Zbl 0946.05053
[3] Brualdi, R. A., Shanny, R. F.: Hamiltonian line graphs. J. Graph Theory 5 (1981), 307-314. DOI 10.1002/jgt.3190050312 | MR 0625072 | Zbl 0437.05041
[4] Catlin, P. A.: A reduction method to find spanning Eulerian subgraphs. J. Graph Theory 12 (1988), 29-44. DOI 10.1002/jgt.3190120105 | MR 0928734 | Zbl 0659.05073
[5] Catlin, P. A., Han, Z.-Y., Lai, H.-J.: Graphs without spannning closed trails. Discrete Math. 160 (1996), 81-91. DOI 10.1016/S0012-365X(95)00149-Q | MR 1417562 | Zbl 0859.05060
[6] Chen, Z.-H.: Hamiltonicity and degrees of adjacent vertices in claw-free graphs. J. Graph Theory 86 (2017), 193-212. DOI 10.1002/jgt.22120 | MR 3684782 | Zbl 1370.05124
[7] Dirac, G. A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3) 2 (1952), 69-81. DOI 10.1112/plms/s3-2.1.69 | MR 0047308 | Zbl 0047.17001
[8] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs: A survey. Discrete Math. 164 (1997), 87-147. DOI 10.1016/S0012-365X(96)00045-3 | MR 1432221 | Zbl 0879.05043
[9] Gould, R. J.: Recent advances on the Hamiltonian problem: Survey III. Graphs Comb. 30 (2014), 1-46. DOI 10.1007/s00373-013-1377-x | MR 3143857 | Zbl 1292.05163
[10] Li, D., Lai, H.-J., Zhan, M.: Eulerian subgraphs and Hamilton-connected line graphs. Discrete Appl. Math. 145 (2005), 422-428. DOI 10.1016/j.dam.2004.04.005 | MR 2112533 | Zbl 1057.05053
[11] Matthews, M. M., Sumner, D. P.: Longest paths and cycles in $K_{1,3}$-free graphs. J. Graph Theory 9 (1985), 269-277. DOI 10.1002/jgt.3190090208 | MR 0797514 | Zbl 0591.05041
[12] Niu, Z., Xiong, L., Zhang, S.: Smallest 2-edge-connected graphs without a spanning trail. Util. Math. 88 (2012), 381-397. MR 2975848 | Zbl 1256.05206
[13] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70 (1997), 217-224. DOI 10.1006/jctb.1996.1732 | MR 1459867 | Zbl 0872.05032
[14] Shao, Y.: Claw-Free Graphs and Line Graphs: Ph.D Thesis. West Virginia University, Morgantown (2005). MR 2707853
[15] Singleton, J. E.: Maximal Nontraceable Graphs: Ph.D Thesis. University of South Africa, Pretoria (2006). MR 2717408
[16] Tian, T.: Degree Conditions for Hamiltonian Properties of Claw-free Graphs: Ph.D Thesis. University of Twente, Enschede (2018).
[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. DOI 10.1016/j.disc.2020.111883 | MR 4073374 | Zbl 1440.05163
[18] Tian, T., Xiong, L.: Traceability on 2-connected line graphs. Appl. Math. Comput. 321 (2018), 463-471. DOI 10.1016/j.amc.2017.10.043 | MR 3732390 | Zbl 07070099
[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. DOI 10.7151/dmgt.2125 | MR 4041969 | Zbl 1439.05131
[20] Veldman, H. J.: On dominating and spanning circuits in graphs. Discrete Math. 124 (1994), 229-239. DOI 10.1016/0012-365X(92)00063-W | MR 1258856 | Zbl 0789.05061
[21] Wang, S., Xiong, L.: Spanning trails in a 2-connected graph. Electron. J. Comb. 26 (2019), Article ID P3.56, 19 pages. DOI 10.37236/8121 | MR 4017309 | Zbl 1420.05089
[22] Xiong, L., Zong, M.: Traceability of line graphs. Discrete Math. 309 (2009), 3779-3785. DOI 10.1016/j.disc.2008.10.012 | MR 2537372 | Zbl 1218.05085
Search
Partner of
