Premium
Factorizations of complete multipartite graphs into generalized cubes
Author(s) -
ElZanati S.,
Vanden Eynden C.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200003)33:3<144::aid-jgt4>3.0.co;2-p
Subject(s) - combinatorics , multipartite , mathematics , cartesian product , vertex (graph theory) , discrete mathematics , graph , disjoint sets , direct product , integer (computer science) , computer science , physics , quantum mechanics , quantum entanglement , quantum , programming language
For a positive integer d , the usual d ‐dimensional cube Q d is defined to be the graph ( K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q ( K k , d ) to be the graph ( K k ) d for positive integers d and k . We investigate the decomposition of the complete multipartite graph K k j× k n − jinto factors that are vertex‐disjoint unions of generalized cubes Q ( K k , d i ), where k is a power of a prime, n and j are positive integers with j ≤ n , and the d i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q d ‐factorizations of K n . © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000