Strong difference families over arbitrary graphs |
| |
Authors: | Marco Buratti Lucia Gionfriddo |
| |
Institution: | 1. Dipartimento di Matematica e Informatica, Università di Perugia, Via Vanvitelli 1, I‐06123 Perugia, Italy;2. Dipartimento di Matematica e Informatica, Università di Catania, Via A. Doria 6, I‐95125 Catania, Italy |
| |
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 Km × 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 T5 or the wheel W6. We also show that sometimes strong difference families lead to regular Γ‐decompositions of a complete graph. We construct, for instance, a regular cube‐decomposition of K16m for any integer m whose prime factors are all congruent to 1 modulo 6. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 443–461, 2008 |
| |
Keywords: | regular graph decomposition relative difference family strong difference family graceful labeling α ‐labeling |
|
|