Decomposition of the complete r-graph into complete r-partite r-graphs

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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 languageEnglish (US)
Pages (from-to)95-100
Number of pages6
JournalGraphs and Combinatorics
Volume2
Issue number1
DOIs
StatePublished - Dec 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Decomposition of the complete r-graph into complete r-partite r-graphs'. Together they form a unique fingerprint.

Cite this