Premium
Strong difference families over arbitrary graphs
Author(s) -
Buratti Marco,
Gionfriddo Lucia
Publication year - 2008
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20201
Subject(s) - mathematics , combinatorics , vertex (graph theory) , multipartite , modulo , symmetric graph , petersen graph , graph , prime (order theory) , discrete mathematics , automorphism , transitive relation , line graph , voltage graph , physics , quantum mechanics , quantum entanglement , quantum
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 Γ‐decompositions of a complete graph. We construct, for instance, a regular cube‐decomposition of K 16m 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