Graphs of Separability at Most Two: Structural Characterizations and Their Consequences

Graphs of separability at most k are defined as graphs in which every two non-adjacent vertices are separated by a set of at most k other vertices. For k ∈ {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. Graphs of separability at most 2 generalize complete graphs, cycles and trees. We prove several characterizations of graphs of separability at most 2 and examine some of their consequences.