A linkage of order k of a graph G is a subgraph with k components, each of which is a path. A linkage is vital if it spans all vertices, and no other linkage connects the same pairs of end vertices. We give a characterization of the graphs with a vital linkage of order 2: they are certain minors of a family of highly structured graphs.
Additional Metadata
Keywords graphs, minors, pathwidth, linkage
MSC Structural characterization of families of graphs (msc 05C75), Graph minors (msc 05C83)
THEME Logistics (theme 3)
Publisher Cornell University Library
Series arXiv.org e-Print archive
Project Matroid Structure for Efficiency
Citation
Mayhew, D, Whittle, G, & van Zwam, S.H.M. (2010). The structure of graphs with a vital linkage of order 2. arXiv.org e-Print archive. Cornell University Library .