Name
Abstract | ||
|---|---|---|
If a graph Gcontains two spanning trees T1, T2such that for each two distinct vertices x, yof G, the ( x, y)-path in each Tihas no common edge and no common vertex except for the two ends, then T1, T2are called two completely independent spanning trees (CISTs) of G, i epsilon{1, 2}. If the subgraph induced by the neighbor set of a vertex uin a graph Gis connected, then uis an eligible vertex of G. An hourglass is a graph with degree 4,2,2,2,2 and ( P-6)(2)denotes the square graph of a path P(6)on six vertices. Araki (2014) [1] proved that if a graph Gsatisfies the Dirac's condition, which is also sufficient condition for hamiltonian graphs, then Gcontains two CISTs. Ryja.cek proposed that a claw-free graph Gis hamiltonian if and only if its Ryja.cek's closure, denoted by cl(G), is hamiltonian. In this paper, we prove that if Gis a {claw, hourglass, (P-6)(2)}-free graph with delta(G) >= 4, then Gcontains two CISTs if and only if cl(G) has two CISTs. The bound of the minimum degree in our result is best possible. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2022.113080 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Claw -free graphs, Eligible vertex, Two CISTs | Journal | 345 |
Issue | ISSN | Citations |
12 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaodong Chen | 1 | 0 | 0.34 |
| Mingchu Li | 2 | 469 | 78.10 |
| Liming Xiong | 3 | 82 | 27.88 |