## Abstract

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 riot equal to three. Furthermore, we present a forbidden induced subgraph characterization of chordal dominating pair graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 353-366 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 15 |

Issue number | 3 |

DOIs | |

State | Published - May 2002 |

## Keywords

- Algorithms
- Asteroidal triple-free graphs
- Dominating pair graphs
- Graph classes

## ASJC Scopus subject areas

- Mathematics(all)