• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Fan, Genghua (Fan, Genghua.) [1] (Scholars:范更华) | Hong, Yanmei (Hong, Yanmei.) [2] (Scholars:洪艳梅) | Liu, Qinghai (Liu, Qinghai.) [3] (Scholars:刘清海)

Indexed by:

EI Scopus SCIE

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:

Completely independent spanning trees (CIST) Line graphs

Community:

  • [ 1 ] [Fan, Genghua]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China
  • [ 2 ] [Liu, Qinghai]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China
  • [ 3 ] [Hong, Yanmei]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350108, Peoples R China

Reprint 's Address:

  • 刘清海

    [Liu, Qinghai]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China

Show more details

Version:

Related Keywords:

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

Online/Total:266/10037833
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1