New graph classes characterized by weak vertex separators and two-pairs

Abstract

A set of vertices whose deletion from a graph would increase the distance between two remaining vertices is called a weak vertex separator of the graph. Two vertices form a two-pair if all chordless paths between them have length . I prove that every inclusion-minimal weak vertex separator of every induced subgraph of a graph induces a complete subgraph if and only if nonadjacent vertices of induced subgraphs of always form two-pairs of ; moreover, this is also true when “complete” and are replaced with “edgeless” and (). The first of the resulting new graph classes generalizes chordal graphs, and the second generalizes unichord-free graphs; they both generalize distance-hereditary graphs and geodetic graphs.

Keywords

• two-pair
• minimal vertex separator
• minimal weak separator
• induced-minimal weak separator
• unichord-free