On spanning disjoint paths in line graphs (Q2637723)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On spanning disjoint paths in line graphs |
scientific article |
Statements
On spanning disjoint paths in line graphs (English)
0 references
14 February 2014
0 references
We call a graph \(G\) spanning \(s\)-connected if for any pair of vertices \(u,v\in V(G)\), \(G\) has a spanning \((s; u, v)\)-path-system, i.e., there exists a subgraph \(H\) consisting of \(s\) internally disjoint \((u,v)\)-paths. If \(G\) has a spanning \((k; u, v)\)-path system, for any integer \(k\) with \(1\leq k\leq s\), we say it has the spanning connectivity \(\kappa^*(G)\). \textit{P. A. Catlin} and \textit{H.-J. Lai} [in: Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, 1988. New York: John Wiley \& Sons Ltd. Wiley-Interscience Publication. 207--222 (1991; Zbl 0841.05067)] proved that if a graph \(G\) has 2 edge-disjoint spanning trees, and if \(L(G)\) is the line graph of \(G\), then \(\kappa^*(L(G))\geq2\) if and only if \(\kappa(L(G))\), the connectivity of the graph \(G\), is \(\geq 3\). This paper extends this result and proves that for any integer \(k\geq2\), if \(G_0\), the core of \(G\), has \(k\) edge-disjoint spanning trees, then \(\kappa^*(L(G))\geq k\) if and only if \(\kappa(L(G))\geq\max\{3,k\}\).
0 references
connectivity
0 references
spanning connectivity
0 references
Hamiltonian linegraph
0 references
Hamiltonian-connected line graph
0 references
supereulerian graphs
0 references
collapsible graphs
0 references