r-domination problems on homogeneously orderable graphs

✍ Scribed by Dragan, Feodor F.; Nicolai, Falk

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 153 KB
• Volume: 30
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199709)30:2<121::aid-net6>3.0.co;2-e

✦ Synopsis

In this paper, we consider r-dominating cliques in homogeneously orderable graphs (a common generalization of dually chordal and distance-hereditary graphs) and their relation to strict r-packing sets. We prove that a homogeneously orderable graph G possesses an r-dominating clique if and only if for any pair of vertices x, y of G d(x, y) °r( x) / r( y) / 1 holds where r : V r ‫ގ‬ is a given vertex function. Furthermore, we show that for homogeneously orderable graphs with r-dominating cliques the cardinality of a maximum strict r-packing set equals the cardinality of a minimum r-dominating clique provided the last parameter is not two. Finally, we present two efficient algorithms: The first one decides whether a given homogeneously orderable graph has an r-dominating clique and, if so, computes both a minimum r-dominating clique and a maximum strict r-packing set of the graph. The second one computes a minimum connected r-dominating set in a homogeneously orderable graph. ᭧ 1997