Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902784 | AKCE International Journal of Graphs and Combinatorics | 2017 | 5 Pages |
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 2. I prove that every inclusion-minimal weak vertex separator of every induced subgraph of a graph G induces a complete subgraph if and only if nonadjacent vertices of induced C4 subgraphs of G always form two-pairs of G; moreover, this is also true when “complete” and C4 are replaced with “edgeless” and K4âe (â
K1,1,2). 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Terry A. McKee,