On perfect Γ‐decompositions of the complete graph |
| |
Authors: | Marco Buratti Anita Pasotti |
| |
Affiliation: | 1. Dipartimento di Matematica e Informatica, Università di Perugia, Via Vanvitelli 1, I‐06123 Perugia, Italy;2. Facoltà di Ingegneria, Dipartimento di Matematica, Università degli Studi di Brescia, Via Valotti 9, I‐25133 Brescia, Italy |
| |
Abstract: | Generalizing the well‐known concept of an i‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph Kv to be i‐perfect if for every edge [x, y] of Kv there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a Γ‐decomposition (Γ‐factorization) of Kv that is i‐perfect for any i not exceeding the diameter of a connected graph Γ will be said a Steiner (Kirkman) Γ‐system of order v. In this article we first observe that as a consequence of the deep theory on decompositions of edge‐colored graphs developed by Lamken and Wilson [Lamken and Wilson, 2000, J Combin Theory Ser A 89, 149–200], there are infinitely many values of v for which there exists an i‐perfect Γ‐decomposition of Kv provided that Γ is an i‐equidistance graph, namely a graph such that the number of pairs of vertices at distance i is equal to the number of its edges. Then we give some concrete direct constructions for elementary abelian Steiner Γ‐systems with Γ the wheel on 8 vertices or a circulant graph, and for elementary abelian 2‐perfect cube‐factorizations. We also present some recursive constructions and some results on 2‐transitive Kirkman Γ‐systems. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 197–209, 2009 |
| |
Keywords: | graph‐decomposition factorization i‐equidistance graph Cayley graph difference family difference matrix |
|
|