Abstract
A λ-hyperfactorization ofK 2n is a collection of 1-factors ofK 2n for which each pair of disjoint edges appears in precisely λ of the 1-factors. We call a λ-hyperfactorizationtrivial if it contains each 1-factor ofK 2n with the same multiplicity γ (then λ=γ(2n−5)!!). A λ-hyperfactorization is calledsimple if each 1-factor ofK 2n appears at most once. Prior to this paper, the only known non-trivial λ-hyperfactorizations had one of the following parameters (or were multipliers of such an example)
-
(i)
2n=2a+2, λ=1 (for alla≥3); cf. Cameron [3];
-
(ii)
2n=12, λ=15 or 2n=24, λ=495; cf. Jungnickel and Vanstone [8].
In the present paper we show the existence of non-trivial simple λ-hyperfactorizations ofK 2n for alln≥5.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Beth, D. Jungnickel, andH. Lenz:Design Theory, Bibliographisches Institut, Mannheim (1985), and Cambridge University Press, Cambridge (1986).
J. A. Bondy, andU. S. R. Murty:Graph Theory with applications, North Holland, New York (1976).
P. J. Cameron:Parallelisms of complete designs. Cambridge University Press, Cambridge (1976).
C. Godsil: Polynomial spaces.Discrete Math.,73 (1988/89), 71–88.
J. W. P. Hirschfeld:Projective geometries over finite fields. Oxford University Press, Oxford (1979).
D. J. Horton: Personal communication.
D. R. Hughes, andF. C. Piper:Projective planes. Springer, Berlin-Heidelberg-New York (1973).
D. Jungnickel, andS. A. Vanstone: Hyperfactorizations of graphs and 5-designs.J. Kuwait Univ., (Sci.)14 (1987), 213–224.
C. W. H. Lam, L. Thiel, S. Swiercz, andJ. McKay: The nonexistence of ovals in a projective plane of order 10,Discrete Math. 45 (1983), 318–321.
R. Mathon: The partial geometriespg(5, 7, 3).Congressus Numerantium,31 (1981), 129–139.
E. Mendelsohn, andA. Rosa: One-factorization of the complete graph — a survey.J. Graph Th. 9 (1985), 43–65.
T. van Trung: The existence of an infinite family of simple 5-designs.Math. Z. 187 (1984), 284–287.
Author information
Authors and Affiliations
Additional information
This is the revised version of an earlier preprint bearing the same title (Research Report CORR 87-51, Dept. of Combinatorics and Optimization, University of Waterloo).
Rights and permissions
About this article
Cite this article
Boros, E., Jungnickel, D. & Vanstone, S.A. The existence of non-trivial hyperfactorizations ofK 2n . Combinatorica 11, 9–15 (1991). https://doi.org/10.1007/BF01375468
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01375468