Two Completely Independent Spanning Trees of P4-Free Graphs

A graph without induced subgraphs isomorphic to a path of length 3 is P-4-free. If a graph G contains two spanning trees T-1, T-2 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 T-1, T(2 )are called two completely independent spanning trees (CISTs) of G, i is an element of {1, 2}. Several results have shown that some sufficient conditions for Hamiltonian graphs may also guarantee the existence of two CISTs. Jung proved that a P4-free graph with at least 3 vertices is Hamiltonian if and only if it is 1-tough. Inspired by these results, in this paper, we prove that a P4-free graph G contains two CISTs if and only if G is a 2-connected graph of order n >= 4 and G is an element of/ K, where K is a family of some graphs. Moreover, we obtain that every 1-tough P4-free graph of order n >= 4 with G is an element of/ K' contains two CISTs, where K' is a family of four graphs.

Automated summary

This paper proves that a P4-free graph G contains two completely independent spanning trees if and only if G is a 2-connected graph and belongs to a specific graph family. Moreover, it is also shown that every 1-tough P4-free graph G, belonging to another graph family, contains two completely independent spanning trees.