Degree sums of adjacent vertices for traceability of claw-free graphs

Tian, Tao ; Xiong, Liming ; Chen, Zhi-Hong ; Wang, Shipeng

Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 313-330

Résumé

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).

Détail

DOI : 10.21136/CMJ.2022.0544-19

Classification : 05C07, 05C38, 05C45
Keywords: traceable graph; line graph; spanning trail; closure