A note on \(r\)-dominating cliques (Q1382816): Difference between revisions

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\).