A note on r-dominating cliques
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\).
- A characterisation of rigid circuit graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A Helly theorem in weakly modular space
- Conditions for invariance of set diameters under d-convexification in a graph
- Dismantling absolute retracts of reflexive graphs
- Distance-hereditary graphs
- Dominating cliques in chordal graphs
- Dominating cliques in distance-hereditary graphs
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Hereditary modular graphs
- scientific article; zbMATH DE number 26592 (Why is no real title available?)
- scientific article; zbMATH DE number 867678 (Why is no real title available?)
- scientific article; zbMATH DE number 1414320 (Why is no real title available?)
- On domination problems for permutation and other graphs
- On local convexity in graphs
- On rigid circuit graphs
- On the Helly property working as a compactness criterion on graphs
- On the semi-perfect elimination
- Perfect Elimination and Chordal Bipartite Graphs
- Pseudo-modular graphs
- The smallest graph variety containing all paths
- Topics on domination
- Weakly triangulated graphs
- \(r\)-dominating cliques in graphs with hypertree structure
- Domination in quadrangle-free Helly graphs
- A note on simplicial cliques
- Helly-gap of a graph and vertex eccentricities
- Helly groups
- Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
- Fine-grained classification of detecting dominating patterns
This page was built for publication: A note on \(r\)-dominating cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382816)
