The concept of a strong difference family formally introduced in Buratti [J Combin Designs 7 (1999), 406-425] with the aim of getting group divisible designs with an automorphism group acting regularly on the points, is here extended for getting, more generally, sharply-vertex-transitive Γ-decompositions of a complete multipartite graph for several kinds of graphs Γ. We show, for instance, that if Γ has e edges, then it is often possible to get a sharply-vertex-transitive Γ-decomposition of $K_{m×e}$ for any integer m whose prime factors are not smaller than the chromatic number of Γ. This is proved to be true whenever Γ admits an α-labeling and, also, when Γ is an odd cycle or the Petersen graph or the prism $T_5$ or the wheel $W_6$. We also show that sometimes strong difference families lead to regular Γ-decomposition of a complete graph. We construct, for instance, a regular cube-decomposition of $K_{16m}$ for any odd integer m whose prime factors are all congruent to 1 modulo 6.

Strong difference families over arbitrary graphs

BURATTI, Marco;
2008

Abstract

The concept of a strong difference family formally introduced in Buratti [J Combin Designs 7 (1999), 406-425] with the aim of getting group divisible designs with an automorphism group acting regularly on the points, is here extended for getting, more generally, sharply-vertex-transitive Γ-decompositions of a complete multipartite graph for several kinds of graphs Γ. We show, for instance, that if Γ has e edges, then it is often possible to get a sharply-vertex-transitive Γ-decomposition of $K_{m×e}$ for any integer m whose prime factors are not smaller than the chromatic number of Γ. This is proved to be true whenever Γ admits an α-labeling and, also, when Γ is an odd cycle or the Petersen graph or the prism $T_5$ or the wheel $W_6$. We also show that sometimes strong difference families lead to regular Γ-decomposition of a complete graph. We construct, for instance, a regular cube-decomposition of $K_{16m}$ for any odd integer m whose prime factors are all congruent to 1 modulo 6.
2008
File in 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/11391/166054
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 28
social impact