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

Tao Tian*, Liming Xiong, Zhi Hong Chen, Shipeng Wang

*此作品的通讯作者

科研成果: 期刊稿件文章同行评审

1 引用 (Scopus)

摘要

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 (Formula presented.). Let H be a 2-connected claw-free simple graph of order n with δ(H) ≥ 3. We show that, if (Formula presented.) and n is sufficiently large, then either H is traceable or the Ryjáček’s closure 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 (Formula presented.) and n is sufficiently large, then H is traceable. The bound 1\3(n - 6) is sharp. As a byproduct, we prove that there are exactly eight graphs in the family 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).

源语言英语
页(从-至)313-330
页数18
期刊Czechoslovak Mathematical Journal
72
2
DOI
出版状态已出版 - 6月 2022

指纹

探究 'Degree sums of adjacent vertices for traceability of claw-free graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此