Every 2-connected {claw, Z2}-free graph with minimum degree at least 4 contains two CISTs

Xiaodong Chen; Jiayuan Zhang; Liming Xiong; Guifu Su

doi:10.1016/j.dam.2024.08.020

Every 2-connected {claw, Z₂}-free graph with minimum degree at least 4 contains two CISTs

Xiaodong Chen^*
, Jiayuan Zhang
, Liming Xiong
, Guifu Su

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

If a graph G contains two spanning trees T₁,T₂ such that for each two distinct vertices x,y of G, the (x,y)-path in each T_i has no common edge and no common vertex except for the two ends, then T₁,T₂ are called two completely independent spanning trees (CISTs) of G,i∈{1,2}. There are several results on the existence of two CISTs. In this paper, we prove that every 2-connected {claw, Z₂}-free graph with minimum degree at least 4 contains two CISTs. The bound of the minimum degree in our result is best possible.

Original language	English
Pages (from-to)	51-64
Number of pages	14
Journal	Discrete Applied Mathematics
Volume	360
DOIs	https://doi.org/10.1016/j.dam.2024.08.020
Publication status	Published - 15 Jan 2025

Keywords

Claw-free graphs
Eligible vertex
Ryjáček's closure
Two CISTs

Access to Document

10.1016/j.dam.2024.08.020

Cite this

@article{74be0894dbc2405d993626c9f9ae584e,

title = "Every 2-connected \{claw, Z2\}-free graph with minimum degree at least 4 contains two CISTs",

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\}. There are several results on the existence of two CISTs. In this paper, we prove that every 2-connected \{claw, Z2\}-free graph with minimum degree at least 4 contains two CISTs. The bound of the minimum degree in our result is best possible.",

keywords = "Claw-free graphs, Eligible vertex, Ryj{\'a}{\v c}ek's closure, Two CISTs",

author = "Xiaodong Chen and Jiayuan Zhang and Liming Xiong and Guifu Su",

note = "Publisher Copyright: {\textcopyright} 2024",

year = "2025",

month = jan,

day = "15",

doi = "10.1016/j.dam.2024.08.020",

language = "English",

volume = "360",

pages = "51--64",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Every 2-connected {claw, Z2}-free graph with minimum degree at least 4 contains two CISTs

AU - Chen, Xiaodong

AU - Zhang, Jiayuan

AU - Xiong, Liming

AU - Su, Guifu

PY - 2025/1/15

Y1 - 2025/1/15

N2 - 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}. There are several results on the existence of two CISTs. In this paper, we prove that every 2-connected {claw, Z2}-free graph with minimum degree at least 4 contains two CISTs. The bound of the minimum degree in our result is best possible.

AB - 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}. There are several results on the existence of two CISTs. In this paper, we prove that every 2-connected {claw, Z2}-free graph with minimum degree at least 4 contains two CISTs. The bound of the minimum degree in our result is best possible.

KW - Claw-free graphs

KW - Eligible vertex

KW - Ryjáček's closure

KW - Two CISTs

UR - https://www.scopus.com/pages/publications/85202847983

U2 - 10.1016/j.dam.2024.08.020

DO - 10.1016/j.dam.2024.08.020

M3 - Article

AN - SCOPUS:85202847983

SN - 0166-218X

VL - 360

SP - 51

EP - 64

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Every 2-connected {claw, Z₂}-free graph with minimum degree at least 4 contains two CISTs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this