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 Wiley
Journal Journal of Graph Theory
Mayhew, D, Whittle, G, & van Zwam, S.H.M. (2011). The structure of graphs with a vital linkage of order 2. Journal of Graph Theory.