✦ LIBER ✦

r-Dominating cliques in graphs with hypertree structure

✍ Scribed by Feodor F. Dragan; Andreas Brandstädt

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 848 KB
Volume: 162
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00277-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 simple necessary and sufficient condition for the existence of r-dominating cliques in the case of Helly graphs and of chordal graphs.

(ii) For Helly graphs with an r-dominating clique the minimum size of an r-dominating clique coincides with the minimum size of any r-dominating set.

(iii) We give a linear-time algorithm for finding a minimum r-dominating clique in dually chordal graphs (a generalization of strongly chordal graphs).

These results improve and extend earlier results on r-dominating cliques in chordal and strongly chordal graphs.

📜 SIMILAR VOLUMES

Dominating cliques in chordal graphs

✍ Dieter Kratsch; Peter Damaschke; Anna Lubiw 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

A chordal graph has a dominating clique iff it has diameter at most 3. A strongly chordal graph which has a dominating clique has one as small as the smallest dominating set-and, furthermore, there is a linear-time algorithm to find such a small dominating clique.

Finding dominating cliques efficiently,

Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

✍ Dieter Kratsch 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 914 KB

We study a new version of the domination problem in which the dominating set is required to be a clique. The minimum dominating clique problem is NP-complete for split graphs and, hence, for chordal graphs. We show that for two other important subclasses of chordal graphs the problem is solvable eff

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Dominating subgraphs in graphs with some

Dominating subgraphs in graphs with some forbidden structures

✍ Jiping Liu; Huishan Zhou 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 387 KB

We characterize the triangle-free graphs with neither induced path of six vertices nor induced cycle of six vertices and the triangle-free graphs without induced path of six vertices in terms of dominating subgraphs.

Kernels in graphs with a clique-cutset

✍ Henry Jacob 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 138 KB

We consider graphs that have a clique-cutset, and we show that this property preserves the existence of a kernel in a certain sense. We consider finite directed graphs that do not have multiple arcs or loops, but there may be symmetric arcs between some pairs of vertices. Let G = (V, A) be a direct

On connectivity in graphs with given cli

On connectivity in graphs with given clique number

✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

## Abstract We consider finite, undirected, and simple graphs __G__ of order __n__(__G__) and minimum degree δ(__G__). The connectivity κ(__G__) for a connected graph __G__ is defined as the minimum cardinality over all vertex‐cuts. If κ(__G__) < δ(__G__), then Topp and Volkmann 7 showed in 1993 f