Two completely independent spanning trees of claw-free graphs

Xiaodong Chen*, Mingchu Li, Liming Xiong

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number113080
JournalDiscrete Mathematics
Volume345
Issue number12
DOIs
Publication statusPublished - Dec 2022

Keywords

  • Claw-free graphs
  • Eligible vertex
  • Two CISTs

Fingerprint

Dive into the research topics of 'Two completely independent spanning trees of claw-free graphs'. Together they form a unique fingerprint.

Cite this