Abstract
For n ≥ r ≥ 1, let fr(n) denote the minimum number q, such that it is possible to partition all edges of the complete r-graph on n vertices into q complete r-partite r-graphs. Graham and Pollak showed that f2(n) =n - 1. Here we observe that f3(n) =n - 2 and show that for every fixed r ≥ 2, there are positive constants c1(r) and c2(r) such that c1(r) ≤fr(n){dot operator}n-[r/2] ≤n2(r) for all n ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.
Original language | English (US) |
---|---|
Pages (from-to) | 95-100 |
Number of pages | 6 |
Journal | Graphs and Combinatorics |
Volume | 2 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1986 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics