Paper Info
Title
On Spanning Disjoint Paths in Line Graphs
Abstract
Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009 ). For a graph G and an integer s > 0 and for $${u, v \in V(G)}$$ with u v , an ( s ; u , v )-path-system of G is a subgraph H consisting of s internally disjoint ( u , v )-paths. A graph G is spanning s-connected if for any $${u, v \in V(G)}$$ with u v , G has a spanning ( s ; u , v )-path-system. The spanning connectivity *( G ) of a graph G is the largest integer s such that G has a spanning ( k ; u , v )-path-system, for any integer k with 1 ≤ k ≤ s , and for any $${u, v \in V(G)}$$ with u v . An edge counter-part of *( G ), defined as the supereulerian width of a graph G , has been investigated in Chen et al. (Supereulerian graphs with width s and s -collapsible graphs, 2012 ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207---222, 1991 ) proved that if a graph G has 2 edge-disjoint spanning trees, and if L ( G ) is the line graph of G , then *( L ( G )) 2 if and only if ( L ( G )) 3. In this paper, we extend this result and prove that for any integer k 2, if G 0, the core of G , has k edge-disjoint spanning trees, then *( L ( G )) k if and only if ( L ( G )) max{3, k }.
Year
DOI
Venue
2013
10.1007/s00373-012-1237-0
Graphs and Combinatorics
Keywords
Field
DocType
hamiltonian-connected line graph,spanning connectivity,collapsible graphs,supereulerian graphs,hamiltonian linegraph,connectivity
Combinatorics,Graph toughness,Line graph,Bound graph,Graph power,Graph factorization,Spanning tree,Symmetric graph,Shortest-path tree,Mathematics
Journal
Volume
Issue
ISSN
29
6
1435-5914
Citations 
PageRank 
References 
4
0.44
8
Authors
5
Name
Order
Citations
PageRank
Ye Chen140.44
Zhi-Hong Chen27011.83
Hong-Jian Lai363197.39
Ping Li4217.14
Erling Wei540.44