On Spanning Disjoint Paths in Line Graphs

Ye Chen, Zhi Hong Chen, Hong Jian Lai, Ping Li, Erling Wei

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 ∈ 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 ∈ 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 ∈ 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 G0, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}.

Original languageEnglish (US)
Pages (from-to)1721-1731
Number of pages11
JournalGraphs and Combinatorics
Volume29
Issue number6
DOIs
StatePublished - Nov 2013
Externally publishedYes

Keywords

  • Collapsible graphs
  • Connectivity
  • Hamiltonian linegraph
  • Hamiltonian-connected line graph
  • Spanning connectivity
  • Supereulerian graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On Spanning Disjoint Paths in Line Graphs'. Together they form a unique fingerprint.

Cite this