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; A., Pasotti. - In: JOURNAL OF COMBINATORIAL DESIGNS. - ISSN 1063-8539. - 17:2(2009), pp. 197-209. [10.1002/jcd.20199]

### On perfect Gamma-decompositions of the complete graph

#### 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.
##### Scheda breve Scheda completa
2009
Graph decomposition; Perfect cycle system
01 Pubblicazione su rivista::01a Articolo in rivista
On perfect Gamma-decompositions of the complete graph / Buratti, Marco; A., Pasotti. - In: JOURNAL OF COMBINATORIAL DESIGNS. - ISSN 1063-8539. - 17:2(2009), pp. 197-209. [10.1002/jcd.20199]
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
• ND
• 11
• 10