Dominating Pair Graphs
Jitender S. Deogun, Dieter Kratsch · SIAM Journal on Discrete Mathematics · 2002
A pair of vertices of a graph is called a dominating pair if the vertex set of every path between these two vertices is a dominating set of the graph. A graph is a weak dominating pair graph if it has a dominating pair. Further, a graph is called a dominating pair graph if each of its connected induced subgraphs is a weak dominating pair graph. Dominating pair graphs form a class of graphs containing interval, permutation, cocomparability, and asteroidal triple-free graphs. Our purpose is to study the structural properties of dominating pair graphs. Our main results are a polar theorem for the dominating pairs in weak dominating pair graphs and an existence theorem for minimum cardinality connected dominating sets that induce a simple path in connected dominating pair graphs of diameter not equal to three. Furthermore, we present a forbidden induced subgraph characterization of chordal dominating pair graphs.