Decomposition of the completer-graph into completer-partiter-graphs |
| |
| Authors: | Noga Alon |
| |
| Affiliation: | 1. Department of Mathematics, Tel Aviv University, Tel Aviv, Israel
2. Department of Mathematics, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA
|
| |
| Abstract: | Forn ≥ r ≥ 1, letf r (n) denote the minimum numberq, such that it is possible to partition all edges of the completer-graph onn vertices intoq completer-partiter-graphs. Graham and Pollak showed thatf 2(n) =n ? 1. Here we observe thatf 3(n) =n ? 2 and show that for every fixedr ≥ 2, there are positive constantsc 1(r) andc 2(r) such thatc 1(r) ≤f r (n)?n ?r/2] ≤n 2(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
