Dominating Pair Graphs
Jitender S. Deogun, Dieter Kratsch
Source record
Source: Crossref
Published: Jan 1, 2002
DOI: 10.1137/s0895480100367111
Open original source ↗Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.