Premium
The structure of graphs with a vital linkage of order 2
Author(s) -
Mayhew Dillon,
Whittle Geoff,
van Zwam Stefan H. M.
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20640
Subject(s) - linkage (software) , combinatorics , mathematics , graph , path (computing) , induced path , discrete mathematics , induced subgraph , longest path problem , chordal graph , computer science , vertex (graph theory) , genetics , gene , biology , programming language
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.