Generalizing the well-known concept of an i-perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a $\Gamma$-decomposition ($\Gamma$-factorization) of a complete graph $K_v$ to be i-perfect if for every edge [x, y] of $K_v$ there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a $\Gamma$-decomposition ($\Gamma$-factorization) of $K_v$ that is i-perfect for any i not exceeding the diameter of a connected graph $\Gamma$ will be said a Steiner (Kirkman) $\Gamma$-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 $\Gamma$-decomposition of $K_v$ provided that $\Gamma$ 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 $\Gamma$-systems with $\Gamma$ 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 $\Gamma$-systems.

On perfect Gamma-decompositions of the complete graph

BURATTI, Marco;
2009

Abstract

Generalizing the well-known concept of an i-perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a $\Gamma$-decomposition ($\Gamma$-factorization) of a complete graph $K_v$ to be i-perfect if for every edge [x, y] of $K_v$ there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a $\Gamma$-decomposition ($\Gamma$-factorization) of $K_v$ that is i-perfect for any i not exceeding the diameter of a connected graph $\Gamma$ will be said a Steiner (Kirkman) $\Gamma$-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 $\Gamma$-decomposition of $K_v$ provided that $\Gamma$ 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 $\Gamma$-systems with $\Gamma$ 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 $\Gamma$-systems.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1654600
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 10
social impact