Packing and covering of the complete graph. II: The trees of order six. (English) Zbl 0578.05013

Roditty, Y.

Ars Comb. 19, 81-93 (1985).

[For part I, see J. Comb. Theory, Ser. A. 35, 213-243 (1983; Zbl 0521.05053).]
It is shown that the maximal number of pairwise edge disjoint trees of order six in the complete graph \(K_ n\), and the minimum number of trees of order six, whose union is \(K_ n\) are [\(\frac{n(n-1)}{10}]\) and \(\{\) \(\frac{n(n-1)}{10}\}\), \(n\geq 9\), respectively. ([x] denotes the largest integer not exceeding x and \(\{\) \(x\}\) the least integer not less than x.)

Reviewer: J.Schwarze

MSC:

05C05	Trees
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35	Extremal problems in graph theory

Keywords:

maximal number of pairwise edge disjoint trees; minimum number of trees of order six