Two completely independent spanning trees of claw-free graphs

Xiaodong Chen*, Mingchu Li, Liming Xiong

*此作品的通讯作者

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

2 引用 (Scopus)

摘要

If a graph G contains two spanning trees T1,T2 such that for each two distinct vertices x,y of G, the (x,y)-path in each Ti has no common edge and no common vertex except for the two ends, then T1,T2 are called two completely independent spanning trees (CISTs) of G,i∈{1,2}. If the subgraph induced by the neighbor set of a vertex u in a graph G is connected, then u is an eligible vertex of G. An hourglass is a graph with degree 4,2,2,2,2 and (P6)2 denotes the square graph of a path P6 on six vertices. Araki (2014) [1] proved that if a graph G satisfies the Dirac's condition, which is also sufficient condition for hamiltonian graphs, then G contains two CISTs. Ryjáček proposed that a claw-free graph G is hamiltonian if and only if its Ryjáček's closure, denoted by cl(G), is hamiltonian. In this paper, we prove that if G is a {claw, hourglass, (P6)2}-free graph with δ(G)≥4, then G contains two CISTs if and only if cl(G) has two CISTs. The bound of the minimum degree in our result is best possible.

源语言英语
文章编号113080
期刊Discrete Mathematics
345
12
DOI
出版状态已出版 - 12月 2022

指纹

探究 'Two completely independent spanning trees of claw-free graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此