Bounds for Overfull Sets of One-Factors

J. P. McSorley and W. D. Wallis

Southern Illinois University Carbondale, Illinois, USA 62901-4408

Abstract

An overfull set of one-factors of K_{2n} is a set of one-factors that between them cover all the edges of K_{2n}, but contain no one-factorization of K_{2n}. We ask how many members such a set can contain, and obtain upper and lower bounds.

1 Introduction

If G is any graph, then a one-factor of G is a subgraph with vertex-set V (G) that is a regular graph of degree 1. In other words, a one-factor is a set of pairwise disjoint edges of G that between them contain every vertex. A one-factorization of G is a decomposition of the edge-set of G into edge-disjoint one-factors. Clearly any graph must have an even number of vertices to possess a one-factor or one-factorization.

In particular, we consider one-factors and one-factorizations of complete graphs. We denote the complete graph on 2n vertices by K_{2n}. We label the vertices of K_{2n} as ∞, 0, 1, ⋯, 2n − 2; the labels are treated as integers modulo 2n − 1 with the proviso that ∞ + 1 = ∞.

We shall denote the set of all one-factors of K_{2n} by A(K_{2n}). It is clear that A(K_{2n}) has (2n − 1)!! elements, where (2n − 1)!! denotes the semifactorial

(2n − 1)!! = (2n − 1) × (2n − 3) × … × 3 × 1 = \frac{(2n)!}{n!2^{n}}.

If (x, y) is any edge of K_{2n}, then there are (2n−3)!! factors containing the edge (x, y). (Essentially, count the one-factors of the K_{2n} produced by deleting x and y.)

We write b(2n) for the number of one-factorizations of K_{2n}. No closed formula for b(2n) is known.

Lemma 1 If F is any one-factor of K_{2n}, let r(F) denote the number of one-factor-izations of K_{2n} of which F is a member. Then

r(F) = \frac{b(2n)}{(2n − 3)!!}.  (1)

Proof. We first observe that r(F) equals the number of one-factorizations of the graph K_{2n} − F. But this graph (the cocktail-party graph on 2n vertices) is unique, independent of the choice of F. So r(F) depends only on 2n.

Now we count all the ordered pairs (F, F), where F is a factor in the factorization F, in two ways, and obtain

(2n − 1)!!r(F) = (2n − 1)b(2n),

which gives the result. □

For convenience we denote this common value by r_{2n}.

2 Overfull sets

Bonisoli [1] introduced the concept of an excessive set of one-factors of K_{2n}. This is a set S of 2n one-factors that covers all edges of K_{2n}, in which no 2n − 1 factors form a one-factorization. Such a set exists for all even orders 2n greater than 4 (see [2, 1]), while orders 2 and 4 are easily seen to be impossible.

We address the more general question: for what values t = |S| does there exist a set S of one-factors of K_{2n} with the following properties:

(1) the members of S cover all edges of K_{2n};

(2) no 2n − 1 members of S form a one-factorization of K_{2n}?

Such a set is called an overfull set of one-factors of K_{2n} of order t.

In particular we ask, what is the greatest order M_{2n} of an overfull set of one-factors of K_{2n}?

3 A lower bound

In [3] there was constructed a set T_{n} of one-factors that covers K_{2n} and contains no one-factorization, when 2n ≥ 8. If F_{i} is the set of all one-factors of K_{2n} containing edge (∞, i). Then

T_{n} = {P_{0}} ∪ D ∪ ⋃_{i=2}^{2n−2} F_{i}

where

P_{0} = {(∞, 0), (1, 2n − 2), …, (k, 2n − k − 1), …, (n − 1, n)},

and D is the set of all one-factors that contain both (∞, 1) and one or more edges from P_{0}.

This set has order

1 + (2n − 3)(2n − 3)!! + ∑_{k=1}^{n−2} (−1)^{k+1}\binom{n − 2}{k}(2n − 2k − 3)!!.

Now M_{6} = 11, and an overfull set of 11 one-factors of K_{6} was presented in [3], so we have

Theorem 1 For all n ≥ 3,

M_{2n} ≥ 1 + (2n − 3)(2n − 3)!! + ∑_{k=1}^{n−2} (−1)^{k+1}\binom{n − 2}{k}(2n − 2k − 3)!!.

4 An upper bound

Suppose R is a set of one-factors of K_{2n} whose complement A(K_{2n})\R is overfull. Then R must contain at least one member of every one-factorization of K_{2n}. Each factor in R belongs to exactly r_{2n} one-factorizations, so R can have non-empty intersection with at most r_{2n}|R| one-factorizations. So

r_{2n}|R| ≥ b(2n).  (2)

Combining (1) and (2) we have

Lemma 2 If R is the complement of an overfull set of one-factors of K_{2n} then

|R| ≥ (2n − 3)!!

Theorem 2 M_{2n} ≤ 2(n − 1)((2n − 3)!!)

Proof. Suppose S is an overfull set with complement R. Then

|S| = |A(K_{2n})| − |R|
= (2n − 1)!! − |R|
≤ (2n − 1)!! − (2n − 3)!!
= 2(n − 1)((2n − 3)!!) □

Combining Theorems 1 and 2, we obtain, for example, 11 ≤ M_{6} ≤ 12 and 81 ≤ M_{8} ≤ 90.

One case that achieves the order |R| = (2n − 3)!! is when R consists of all the one-factors containing a given edge (x, y). In this case the complement of R does not cover (x, y), so it is not overfull. In particular, when 2n = 6, these sets are the only possible sets R with (2n − 3)!! elements, so M_{6} < 2(3 − 1)((6 − 3)!!) = 12. Combined with Theorem 1, this shows that M_{6} = 11. Is it true that |R| = (2n − 3)!! can only be achieved when R consists of all the one-factors containing a given edge?

References

[1] A. Bonisoli, Excessive factorizations of complete graphs, preprint.

[2] D. R. Stinson and W. D. Wallis, An even-side analogue of Room squares. Aeq. Math. 27 (1984), 201–213.

[3] W. D. Wallis, Overfull sets of one-factors. Congressus Num. (to appear).