Decomposition of the completer-graph into completer-partiter-graphs
Decomposition of the completer-graph into completer-partiter-graphs
复制标题
将完整图分解为完整部分图
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
Noga Alon
中科院分区：
文献类型：
--
作者：
Noga Alon
对于n ≥ r ≥ 1，让fr(n)表示最小数q，即有可能将n个顶点上的完形图的所有边分割成q个完形分割图。格雷厄姆和波拉克证明了 f2(n) =n - 1。在这里，我们观察到 f3(n) =n - 2，并证明对于每个固定的 r ≥ 2，都存在正常数 c1(r) 和 c2(r)，使得对于所有 n ≥ r，c1(r) ≤fr(n)⋅n-[r/2] ≤n2(r)。证明使用了一些简单的线性代数思想。
Forn ≥ r ≥ 1, letfr(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 thatf2(n) =n − 1. Here we observe thatf3(n) =n − 2 and show that for every fixedr ≥ 2, there are positive constantsc1(r) andc2(r) such thatc1(r) ≤fr(n)⋅n−[r/2] ≤n2(r) for alln ≥ r. This solves a problem of Aharoni and Linial. The proof uses some simple ideas of linear algebra.