Back to Search
Start Over
On Spanning Disjoint Paths in Line Graphs.
- Source :
-
Graphs & Combinatorics . Nov2013, Vol. 29 Issue 6, p1721-1731. 11p. - Publication Year :
- 2013
-
Abstract
- Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, ). 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, ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207-222, ) 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, the core of G, has k edge-disjoint spanning trees, then κ*( L( G)) ≥ k if and only if κ( L( G)) ≥ max{3, k}. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 29
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 91661162
- Full Text :
- https://doi.org/10.1007/s00373-012-1237-0