𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Covering all cliques of a graph

✍ Scribed by Zsolt Tuza

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
701 KB
Volume
86
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

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 cliques of a graph with ver
Covering the cliques of a graph with vertices
✍ Paul ErdΕ‘s; Tibor Gallai; Zsolt Tuza πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 681 KB

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.

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