A note on \(r\)-dominating cliques
type: Item
instance of: scholarly article
title: A note on \(r\)-dominating cliques
zbMATH Open document ID: 0891.05056
DOI: 10.1016/S0012-365X(97)00076-9
author: Victor Chepoi
published in: Discrete Mathematics
publication date: 1998-07-06T00:00:00Z
review text: Associated with every vertex \(v\) of a connected, but not necessarily finite graph \(G=(V,E)\) is a non-negative integer \(r(v)\), its dominating radius. A complete subgraph \(C\) of \(G\) is an \(r\)-dominating clique of a subset \(M\) of \(V\) if every vertex \(v\) of \(M\) is distant at most \(r(v)\) from (some vertex of) \(C\). An induced subgraph \(H=(V',E')\) of \(G\) is isometric if \(d_H(u,v)=d_G(u,v)\) for all vertices of \(u\), \(v\) of \(H\). Theorem. For any graph \(G=(V,E)\) the following conditions are equivalent: (1) Every finite subset \(M\) of \(V\) for which \(d_G(u,v)\leq r(u)+r(v)+1\), for all \(u,v\in M\), has an \(r\)-dominating clique in every isometric subgraph \(H\) ``comprising'' \(M\); and (2) \(G\) contains none of the following as an isometric subgraph: the ``house'' (a pentagon with one diagonal), the ``3-deltoid'' (the 10-vertex graph obtained from a 6-wheel by adjoining 3 new vertices, each adjacent to two adjacent rim vertices, the three pairs of rim vertices being disjoint), or any \(n\)-cycle with \(n\geq 5\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1130765
zbMATH Keywords: dominating radius
zbMATH Keywords: \(r\)-dominating clique
zbMATH Keywords: isometric subgraph
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Hereditary modular graphs
cites work: A Helly theorem in weakly modular space
cites work: Pseudo-modular graphs
cites work: Distance-hereditary graphs
cites work: Q4873790
cites work: Dismantling absolute retracts of reflexive graphs
cites work: On domination problems for permutation and other graphs
cites work: A characterisation of rigid circuit graphs
cites work: Q3983321
cites work: On rigid circuit graphs
cites work: Dominating cliques in distance-hereditary graphs
cites work: Q4942657
cites work: On local convexity in graphs
cites work: Perfect Elimination and Chordal Bipartite Graphs
cites work: Weakly triangulated graphs
cites work: Topics on domination
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: On the semi-perfect elimination
cites work: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
cites work: Dominating cliques in chordal graphs
cites work: The smallest graph variety containing all paths
cites work: On the Helly property working as a compactness criterion on graphs
cites work: Conditions for invariance of set diameters under d-convexification in a graph
description: scientific article; zbMATH DE number 1130765