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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references