Graphs of separability at most 2

We introduce graphs of separability at most k as graphs in which every two non-adjacent vertices are separated by a set of at most k other vertices. Graphs of separability at most k arise in connection with the Parsimony Haplotyping problem from computational biology. For is an element of {0, 1} the only connected graphs of separability at most k are complete graphs and block graphs, respectively. For k >= 3, graphs of separability at most k form a rich class of graphs containing all graphs of maximum degree k. We prove several characterizations of graphs of separability at most 2, which generalize complete graphs, cycles and trees. The main result is that every connected graph of separability at most 2 can be constructed from complete graphs and cycles by pasting along vertices or edges, and vice versa, every graph constructed this way is of separability at most 2. The structure theorem has nice algorithmic implications some of which cannot be extended to graphs of higher separability-however certain optimization problems remain intractable on graphs of separability 2. We then characterize graphs of separability at most 2 in terms of minimal forbidden induced subgraphs and minimal forbidden induced minors. Finally, we discuss the possibilities of extending these results to graphs of higher separability. (C) 2011 Elsevier B.V. All rights reserved.