𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dominating cliques in P5-free graphs

✍ Scribed by G. Bacsó; Zs. Tuza

Publisher
Springer Netherlands
Year
1990
Tongue
English
Weight
372 KB
Volume
21
Category
Article
ISSN
0031-5303

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Dominating cliques in chordal graphs
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.

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

Large Cliques in-Free Graphs
Large Cliques in-Free Graphs
✍ András Gyárfás; Alice Hubenko; József Solymosi 📂 Article 📅 2002 🏛 Springer-Verlag 🌐 English ⚖ 130 KB
Weighted parameters in (P5, P5)-free gra
Weighted parameters in (P5, P5)-free graphs
✍ Vassilis Giakoumakis; Irena Rusu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 488 KB

We use the modular decomposition to give O(n(m + n)) algorithms for finding a maximum weighted clique (respectively stable set) and an approximate weighted colouring (respectively partition into cliques) in a (&,E)-free graph. As a by-product, we obtain an O(m+n) algorithm for finding a minimum weig

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