Indexed by:
Abstract:
Two edge-disjoint spanning trees of a graph G are completely independent if the two paths connecting any two vertices of G 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 G is a graph on n vertices in which each pair of non-adjacent vertices have degree-sum at least n, then G 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. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE APPLIED MATHEMATICS
ISSN: 0166-218X
Year: 2014
Volume: 177
Page: 95-100
0 . 8 0 2
JCR@2014
1 . 0 0 0
JCR@2023
ESI Discipline: ENGINEERING;
ESI HC Threshold:184
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 42
SCOPUS Cited Count: 47
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: