Back to Search
Start Over
DOMINATING PAIR GRAPHS.
- Source :
- SIAM Journal on Discrete Mathematics; 2002, Vol. 15 Issue 3, p353-366, 14p
- Publication Year :
- 2002
-
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 not equal to three. Furthermore, we present a forbidden induced subgraph characterization of chordal dominating pair graphs. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPHIC methods
GEOMETRICAL drawing
ALGORITHMS
ALGEBRA
PERMUTATIONS
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 15
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 12856374
- Full Text :
- https://doi.org/10.1137/S0895480100367111