Equipartite Gregarious 5-Cycle Systems and Other Results |
| |
Authors: | Benjamin R Smith |
| |
Institution: | (1) Centre for Discrete Mathematics and Computing, Department of Mathematics, The University of Queensland, Queensland, 4072, Australia |
| |
Abstract: | A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite 3-cycle systems are 3-GDDs (and so are automatically gregarious), and necessary and sufficient
conditions for their existence are known. The cases of equipartite gregarious 4-, 6- and 8-cycle systems have also been dealt
with (using techniques that could be applied in the case of any even length cycle). Here we give necessary and sufficient conditions for the existence of a gregarious 5-cycle decomposition of
the complete equipartite graph Km(n) (in effect the first odd length cycle case for which the gregarious constraint has real meaning). In doing so, we also define some general cyclic
constructions for the decomposition of certain complete equipartite graphs into gregarious p-cycles (where p is an odd prime). |
| |
Keywords: | Graph decomposition gregarious cycle equipartite graph |
本文献已被 SpringerLink 等数据库收录! |
|