Sharp bounds for decompositions of graphs into completer-partite subgraphs
✍ Scribed by Gregory, David A.; Vander Meulen, Kevin N.
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 435 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 e prove that m,(G) 2 log,(n + rl)/r. Furthermore, for each k 2 0 and r 2 2, there is a unique reduced graph G = G(r, k) with m,(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m,(G) 2 max{n+(G), n-(G)/(r -I)}, and show that equality holds if G = G(r, k).