𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Covering the edges of a random graph by cliques

✍ Scribed by Alan Frieze; Bruce Reed

Publisher
Springer-Verlag
Year
1995
Tongue
English
Weight
267 KB
Volume
15
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Clique coverings of the edges of a rando
Clique coverings of the edges of a random graph
✍ BΓ©la BollobΓ‘s; Paul ErdΕ‘s; Joel Spencer; Douglas B. West πŸ“‚ Article πŸ“… 1993 πŸ› Springer-Verlag 🌐 English βš– 293 KB
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.

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.

Covering the Edges of a Connected Graph
Covering the Edges of a Connected Graph by Paths
✍ L. Pyber πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 316 KB

We prove that every connected graph on n vertices can be covered by at most nΓ‚2+O(n 3Γ‚4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.