๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On a clique covering problem of orlin

โœ Scribed by David A. Gregory; Norman J. Pullman

Publisher
Elsevier Science
Year
1982
Tongue
English
Weight
261 KB
Volume
41
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let Tz, be the complement of a perfect matching in the complete ,qraph on 2n vertkes, am; cc(T?,I be the minimum #lumber of complete subgraphs necessary to cover all rhe edge? cf T2,,. Orlin posed the problem of determining the asymptotic behzviour of cc(T,,!. We show that cc( T,,

๐Ÿ“œ 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 all cliques of a graph
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 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