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

Tian, Tao, et al. "Degree sums of adjacent vertices for traceability of claw-free graphs." Czechoslovak Mathematical Journal 72.2 (2022): 313-330. <http://eudml.org/doc/298307>.

@article{Tian2022,
abstract = {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 \lbrace d(u) + d(v) \colon uv \in E(H)\rbrace $. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta (H)\ge 3$. We show that, if $\bar\{\sigma \}_2 (H) \ge \frac\{1\}\{7\} (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\{1\}\{3\} (n-6)$ and $n$ is sufficiently large, then $H$ is traceable. The bound $\frac\{1\}\{3\} (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).},
author = {Tian, Tao, Xiong, Liming, Chen, Zhi-Hong, Wang, Shipeng},
journal = {Czechoslovak Mathematical Journal},
keywords = {traceable graph; line graph; spanning trail; closure},
language = {eng},
number = {2},
pages = {313-330},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Degree sums of adjacent vertices for traceability of claw-free graphs},
url = {http://eudml.org/doc/298307},
volume = {72},
year = {2022},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 2
SP - 313
EP - 330
AB - 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 \lbrace d(u) + d(v) \colon uv \in E(H)\rbrace $. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta (H)\ge 3$. We show that, if $\bar{\sigma }_2 (H) \ge \frac{1}{7} (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{1}{3} (n-6)$ and $n$ is sufficiently large, then $H$ is traceable. The bound $\frac{1}{3} (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).
LA - eng
KW - traceable graph; line graph; spanning trail; closure
UR - http://eudml.org/doc/298307
ER -