Dominating pair graphs

Jitender S. Deogun, Dieter Kratsch

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)353-366
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume15
Issue number3
DOIs
StatePublished - May 2002

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Dominating pair graphs'. Together they form a unique fingerprint.

Cite this