期刊
DISCRETE APPLIED MATHEMATICS
卷 177, 期 -, 页码 95-100出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2014.06.002
关键词
Completely independent spanning trees (CIST); Line graphs
资金
- NSFC [11301086, 11326214]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据