𝔖 Bobbio Scriptorium
✦   LIBER   ✦

How many graphs are unions of k-cliques?

✍ Scribed by Béla Bollobás; Graham R. Brightwell

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
171 KB
Volume
52
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study the number $ F [n;k] $ of n‐vertex graphs that can be written as the edge‐union of k‐vertex cliques. We obtain reasonably tight estimates for $ F [n;k] $ in the cases (i) k = n − o(n) and (ii) k = o(n) but $ k/log, n \to\infty $. We also show that $ F [n;k] $ exhibits a phase transition around $ k = log_2 n $. We leave open several potentially interesting cases, and raise some other questions of a similar nature. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 87–107, 2006

📜 SIMILAR VOLUMES

How many species of Cladocera are there?
How many species of Cladocera are there?
✍ N. M. Korovchinsky 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 831 KB

An estimation of the number of taxa within families, genera and local faunas of Cladocera reveals that only c . 129 species (17% of all known species) may be considered as sufficiently well described (valid species), and c . 146 as rather well described (fair species) but needing further study using

The clique numbers of regular graphs of
The clique numbers of regular graphs of matrix algebras are finite
✍ S. Akbari; M. Jamaali; S.A. Seyed Fakhari 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 96 KB

Let F be a field, char(F) / = 2, and S ⊆ GL n (F), where n is a positive integer. In this paper we show that if for every distinct elements x, y ∈ S, x + y is singular, then S is finite. We conjecture that this result is true if one replaces field with a division ring.

How many fold types of protein are there
How many fold types of protein are there in nature?
✍ Wang, Zhi-Xin 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 486 KB

Many protein structures have now been determined and reveal that protein molecules can adopt the same fold despite having very different sequences. It has been suggested that, owing to different stereochemical constraints, the number of ways that a sequence can fold may be limited. Therefore, it is