Geodesic
Degree sums of adjacent vertices for traceability of claw-free graphs
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 313-330
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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).
DOI : 10.21136/CMJ.2022.0544-19
Classification : 05C07, 05C38, 05C45
Keywords: traceable graph; line graph; spanning trail; closure 
@article{10_21136_CMJ_2022_0544_19,
     author = {Tian, Tao and Xiong, Liming and Chen, Zhi-Hong and Wang, Shipeng},
     title = {Degree sums of adjacent vertices for traceability of claw-free graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {313--330},
     year = {2022},
     volume = {72},
     number = {2},
     doi = {10.21136/CMJ.2022.0544-19},
     mrnumber = {4412761},
     zbl = {07547206},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0544-19/}
}
TY  - JOUR
AU  - Tian, Tao
AU  - Xiong, Liming
AU  - Chen, Zhi-Hong
AU  - Wang, Shipeng
TI  - Degree sums of adjacent vertices for traceability of claw-free graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2022
SP  - 313
EP  - 330
VL  - 72
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0544-19/
DO  - 10.21136/CMJ.2022.0544-19
LA  - en
ID  - 10_21136_CMJ_2022_0544_19
ER  - 
%0 Journal Article
%A Tian, Tao
%A Xiong, Liming
%A Chen, Zhi-Hong
%A Wang, Shipeng
%T Degree sums of adjacent vertices for traceability of claw-free graphs
%J Czechoslovak Mathematical Journal
%D 2022
%P 313-330
%V 72
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0544-19/
%R 10.21136/CMJ.2022.0544-19
%G en
%F 10_21136_CMJ_2022_0544_19
Tian, Tao; Xiong, Liming; Chen, Zhi-Hong; Wang, Shipeng. Degree sums of adjacent vertices for traceability of claw-free graphs. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 313-330. doi: 10.21136/CMJ.2022.0544-19

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, New York (2008). | DOI | MR | JFM

[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 | MR | JFM

[3] Brualdi, R. A., Shanny, R. F.: Hamiltonian line graphs. J. Graph Theory 5 (1981), 307-314. | DOI | MR | JFM

[4] Catlin, P. A.: A reduction method to find spanning Eulerian subgraphs. J. Graph Theory 12 (1988), 29-44. | DOI | MR | JFM

[5] Catlin, P. A., Han, Z.-Y., Lai, H.-J.: Graphs without spannning closed trails. Discrete Math. 160 (1996), 81-91. | DOI | MR | JFM

[6] Chen, Z.-H.: Hamiltonicity and degrees of adjacent vertices in claw-free graphs. J. Graph Theory 86 (2017), 193-212. | DOI | MR | JFM

[7] Dirac, G. A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3) 2 (1952), 69-81. | DOI | MR | JFM

[8] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs: A survey. Discrete Math. 164 (1997), 87-147. | DOI | MR | JFM

[9] Gould, R. J.: Recent advances on the Hamiltonian problem: Survey III. Graphs Comb. 30 (2014), 1-46. | DOI | MR | JFM

[10] Li, D., Lai, H.-J., Zhan, M.: Eulerian subgraphs and Hamilton-connected line graphs. Discrete Appl. Math. 145 (2005), 422-428. | DOI | MR | JFM

[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 | MR | JFM

[12] Niu, Z., Xiong, L., Zhang, S.: Smallest 2-edge-connected graphs without a spanning trail. Util. Math. 88 (2012), 381-397. | MR | JFM

[13] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70 (1997), 217-224. | DOI | MR | JFM

[14] Shao, Y.: Claw-Free Graphs and Line Graphs: Ph.D Thesis. West Virginia University, Morgantown (2005). | MR

[15] Singleton, J. E.: Maximal Nontraceable Graphs: Ph.D Thesis. University of South Africa, Pretoria (2006). | MR

[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 | MR | JFM

[18] Tian, T., Xiong, L.: Traceability on 2-connected line graphs. Appl. Math. Comput. 321 (2018), 463-471. | DOI | MR | JFM

[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 | MR | JFM

[20] Veldman, H. J.: On dominating and spanning circuits in graphs. Discrete Math. 124 (1994), 229-239. | DOI | MR | JFM

[21] Wang, S., Xiong, L.: Spanning trails in a 2-connected graph. Electron. J. Comb. 26 (2019), Article ID P3.56, 19 pages. | DOI | MR | JFM

[22] Xiong, L., Zong, M.: Traceability of line graphs. Discrete Math. 309 (2009), 3779-3785. | DOI | MR | JFM

Cité par Sources :