𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on r-dominating cliques

✍ Scribed by Victor Chepoi

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
670 KB
Volume
183
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let M be a finite subset of vertices of a connected graph G and assume that every vertex v E M has a dominating radius r(v)E N U {0}. A complete subgraph C is an r-dominating clique of M if every vertex vEM is at distance at most r(v) from C. Even for r(v)~ 1 the problem whether or not a given graph has an r-dominating clique is NP-complete. Evidently, if M admits an r-dominating clique then d(u, v) <~ r(u) + r(v) + 1 for any u, v E M. We characterize the graphs G for which this condition guarantees the existence of r-dominating cliques not only in G but also in all isometric subgraphs of G comprising M. These are the graphs which do not contain the house, the 3-deltoid, or any n-cycle with n ~> 5 as an isometric subgraph.

πŸ“œ SIMILAR VOLUMES

r-Dominating cliques in graphs with hype
r-Dominating cliques in graphs with hypertree structure
✍ Feodor F. Dragan; Andreas BrandstΓ€dt πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 848 KB

Let G = (V, E) be an undirected graph and r be a vertex weight function with positive integer values. A subset (clique) D ~\_ V is an r-dominating set (clique) in G ifffor every vertex v e V there is a vertex u e D with dist(u, v) <~ r(v). This paper contains the following results: (i) We give a si

A note on distance-dominating cycles
A note on distance-dominating cycles
✍ P. Fraisse πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 396 KB

Nous prouvons une conjecture due & Bondy et Fan. Un cycle C d'un graphe G est dit m-dominant si tout sommet de V(G -C) est a distance au plus m de C. Notre r&t&at est: si G est k-connexe, et si G n'a pas de cycle m-dominant, alors il existe un stable de cardinal k + 1, dont les sommets sont deux 3 d

A note on cliques and independent sets
A note on cliques and independent sets
✍ Entringer, Roger C.; Goddard, Wayne; Henning, Michael A. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 58 KB πŸ‘ 2 views

For integers m, n β‰₯ 2, let f (m, n) be the minimum order of a graph where every vertex belongs to both a clique of cardinality m and an independent set of cardinality n. We show that f (m, n) = ( √ m -1 + √ n -1) 2 .