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 T i 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 ∈ { 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 P 4 -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 P 4 -free graph G contains two CISTs if and only if G is a 2-connected graph of order n ≥ 4 and G ∉ K , where K is a family of some graphs. Moreover, we obtain that every 1-tough P 4 -free graph of order n ≥ 4 with G ∉ K ′ contains two CISTs, where K ′ is a family of four graphs. [ABSTRACT FROM AUTHOR]