Czechoslovak Mathematical Journal, Vol. 72, No. 2, pp. 313-330, 2022
Degree sums of adjacent vertices for traceability of claw-free graphs
Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang
Received December 24, 2019. Published online February 3, 2022.
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\{ 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)\geq3$. We show that, if $\bar{\sigma}_2 (H) \geq\frac17 (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) > \frac13 (n-6)$ and $n$ is sufficiently large, then $H$ is traceable. The bound $\frac13 (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).
Keywords: traceable graph; line graph; spanning trail; closure
Affiliations: Tao Tian (corresponding author), School of Mathematics and Statistics, Fujian Normal University, No. 1, Science and Technology Road, Shangjie Town, Minhou County, Fuzhou, Fujian, 350117, P. R. China, School of Mathematics and Statistics, Beijing Institute of Technology, No. 9, Liangxiang East Road, Fangshan District, Beijing, 102488, P. R. China, e-mail: taotian0118@163.com; Liming Xiong, Shipeng Wang, School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, No. 9, Liangxiang East Road, Fangshan District, Beijing, 102488, P. R. China, e-mail: lmxiong@bit.edu.cn, spwang22@yahoo.com; Zhi-Hong Chen, Department of Computer Science and Software Engineering, Butler University, 4600 Sunset Avenue, Indianapolis, Indiana 46208-3485, USA, Chen@Butler.edu
