| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418291 | Discrete Applied Mathematics | 2014 | 6 Pages |
Two edge-disjoint spanning trees of a graph GG are completely independent if the two paths connecting any two vertices of GG in the two trees are internally disjoint. It has been asked whether sufficient conditions for hamiltonian graphs are also sufficient for the existence of two completely independent spanning trees (CISTs). We prove that it is true for the classical Ore-condition. That is, if GG is a graph on nn vertices in which each pair of non-adjacent vertices have degree-sum at least nn, then GG has two CISTs. It is known that the line graph of every 4-edge connected graph is hamiltonian. We prove that this is also true for CISTs: the line graph of every 4-edge connected graph has two CISTs. Thomassen conjectured that every 4-connected line graph is hamiltonian. Unfortunately, being 4-connected is not enough for the existence of two CISTs in line graphs. We prove that there are infinitely many 4-connected line graphs that do not have two CISTs.
