✦ LIBER ✦

Covering the cliques of a graph with vertices

✍ Scribed by Paul Erdős; Tibor Gallai; Zsolt Tuza

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 681 KB
Volume: 108
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90681-5

No coin nor oath required. For personal study only.

✦ Synopsis

The following problem is investigated.

Given an undirected graph G, determine the smallest cardinality of a vertex set that meets all complete subgraphs KC G maximal under inclusion.

📜 SIMILAR VOLUMES

Covering all cliques of a graph

✍ Zsolt Tuza 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 701 KB

The following conjecture of T. Gallai is proved: If G is a chordal graph on n vertices, such that all its maximal complete subgraphs have order at least 3, then there is a vertex set of cardinality ~n/3 which meets all maximal complete subgraphs of G. Further related results are given.

On covering all cliques of a chordal gra

On covering all cliques of a chordal graph

✍ Thomas Andreae; Carsten Flotow 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 205 KB

For a graph G = (V,E), a vertex set XC\_ V is called a clique if Ixl>~2 and the graph G [X] induced by X is a complete subgraph maximal under inclusion. We say that a vertex set T is a clique-transversal set if T N X ~ 0 for all cliques X of G, and define the clique-transversal number re(G) as the m

Covering the vertices of a graph by cycl

Covering the vertices of a graph by cycles of prescribed length

✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

Matching and covering the vertices of a

Matching and covering the vertices of a random graph by copies of a given graph

✍ Andrzej Ruciński 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 747 KB

## Rucidski, A., Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics 105 (1992) 185-197. In this paper we partially answer the question: how slowly must p(n) converge to 0 so that a random graph K(n, p) has property PM, almost surely, where PM, me

Asymptotic Clique Covering Ratios of Dis

Asymptotic Clique Covering Ratios of Distance Graphs

✍ Daphne D.-F Liu; Xuding Zhu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 126 KB

Given a finite set D of positive integers, the distance graph G(Z , D) has Z as the vertex set and {i j : |i -j| ∈ D} as the edge set. Given D, the asymptotic clique covering ratio is defined as S(D) = lim sup n→∞ n cl(n) , where cl(n) is the minimum number of cliques covering any consecutive n vert

On the number of distinct minimal clique

On the number of distinct minimal clique partitions and clique covers of a line graph

✍ Sean McGuinness; Rolf Rees 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 812 KB

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculab