𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Clique numbers of graphs

✍ Scribed by Paul Erdös; Marcel Erné

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
337 KB
Volume
59
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For each natural number n, denote by G(n) the set of all numbers c such that there exists a graph with exactly c cliques (i.e., complete subgraphs) and n vertices. We prove the asymptotic estimate Ia(n)l = 0(2"n -z/5) and show that all natural numbers between n + 1 and 2 "-6"5~6 belong to G(n). Thus we obtain IG(n)l lira 2" = 0, while lim IG(n)[ = ~ for all 0 < a < 2. ,._..~ a n Many graph-theoretical problems involve the study of cliques, i.e., complete subgraphs (not necessarily maximal). In this context the following combinatorial problem arises naturally: For which numbers n and c is there a graph with n vertices and exactly c cliques? For fixed n, let G(n) denote the set of all such

📜 SIMILAR VOLUMES

The maximum number of cliques in dense g
The maximum number of cliques in dense graphs
✍ Bruce Hedman 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Denote the number of vertices of G by ]G[. A clique of graph G is a maximal complete subgraph. The density oJ(G) is the number of vertices in the largest clique of G. If ¢o(G)>~½ ]GI, then G has at most 2 t°l-'cG) cliques. The extremal graphs are then examined as wen. ## Terminology We will be co

Clique graphs of packed graphs
Clique graphs of packed graphs
✍ Iwao Sato 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 129 KB

Let IGI be the number of vertices of a graph G and to(G) be the density of G. We call a graph G packed if the clique graph K(G) of G has exactly 2 IGI-O'(G) cliques. We correct the characterization of clique graphs of packed graphs given in Theorem 3.2 of Hedman [3]. All graphs considered here are f

On local connectivity of graphs with giv
On local connectivity of graphs with given clique number
✍ Andreas Holtkamp; Lutz Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract For a vertex __v__ of a graph __G__, we denote by __d__(__v__) the __degree__ of __v__. The __local connectivity__ κ(__u, v__) of two vertices __u__ and __v__ in a graph __G__ is the maximum number of internally disjoint __u__ –__v__ paths in __G__, and the __connectivity__ of __G__ is