✦ LIBER ✦

Bounds on the number of complete subgraphs

✍ Scribed by David C. Fisher; Jennifer Ryan

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 385 KB
Volume: 103
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90323-8

No coin nor oath required. For personal study only.

✦ Synopsis

Fisher, D.C. and J. Ryan, Bounds on the number of complete subgraphs, Discrete Mathematics 103 (1992) 313-320.

Let G be a graph with a clique number w. For 1 s s w, let k, be the number of complete j subgraphs on j nodes. We show that k,,, c (j~l)(kj/(~))u""'. This is exact for complete balanced w-partite graphs and gives Turan' theorem when j = 1.

A corollary is w 3 (8/c: -9k: + 3ks 16k: + 9k:)/(4k: -18k$. This new bound on the clique number supercedes an earlier bound from Turan's theorem.

Let G be a simple graph. Let w (the clique number) be the size of the largest complete subgraph in G. For 1 =~j s W, let kj be the number of complete subgraphs on j nodes (so G has k, nodes, k, edges, k3 triangles, etc.). The main result of this paper is:

(k&l> (LL)*'z2 (L5)'"a. . .a ($j,"".

(1) This is exact for a complete balanced w-partite graph.

The first inequality of (1) can be written as k2 s (w -l)k:/(2w). This is a slightly weakened form of Turan's theorem [9]. The second inequality is a new bound on the number of triangles, k3, in a graph with k2 edges and clique number, W.

📜 SIMILAR VOLUMES

On the Density of Subgraphs in a Graph w

On the Density of Subgraphs in a Graph with Bounded Independence Number

✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

Sharp bounds for decompositions of graph

Sharp bounds for decompositions of graphs into completer-partite subgraphs

✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w

On complete subgraphs of color-critical

On complete subgraphs of color-critical graphs

✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A graph G is called k-critical if x(G) = k and x(G -e) -C x(G) for each edge e of G, where x denotes the chromatic number. T. Gallai conjectured that every k-critical graph of order n contains at most n complete (kl)-subgraphs. In 1987, Stiebitz proved Gallai's conjecture in the case k = 4, and in 1

On complete subgraphs of r-chromatic gra

On complete subgraphs of r-chromatic graphs

✍ B. Bollobás; P. Erdös; E. Szemerédi 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 518 KB

Bounds on chromatic numbers of multiple

Bounds on chromatic numbers of multiple factors of a complete graph

✍ Ján Plesník 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB 👁 1 views

## Abstract Bounds on the sum and product of the chromatic numbers of __n__ factors of a complete graph of order __p__ are shown to exist. The well‐known theorem of Nordhaus and Gaddum solves the problem for __n__ = 2. Strict lower and some upper bounds for any __n__ and strict upper bounds for __n

Forbidden subgraphs and bounds on the si

Forbidden subgraphs and bounds on the size of a maximum matching

✍ Michael D. Plummer; Akira Saito 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let __K__~1,__n__~ denote the star on __n__ + 1 vertices; that is, __K__~1,__n__~ is the complete bipartite graph having one vertex in the first vertex class of its bipartition and __n__ in the second. The special graph __K__~1,3~, called the __claw__, has received much attention in the