Multidesigns for the graph pair formed by the 6-cycle and 3-prism

Yizhe Gao (Illinois Wesleyan University, Bloomington, IL, USA)
Dan Roberts (Illinois Wesleyan University, Bloomington, IL, USA)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 8, No 1 (2020): Electronic Journal of Graph Theory and Applications

Given two graphs G and H, a (G,H)-multidecomposition of Kn is a partition of the edges of Kn into copies of G and H such that at least one copy of each is used. We give necessary and sufficient conditions for the existence of (C6,Ċ6)-multidecomposition of Kn where C6 denotes a cycle of length 6 and C6 denotes the complement of C6. We also characterize the cardinalities of leaves and paddings of maximum (C6,Ċ6)-multipackings and minimum (C6,Ċ6)-multicoverings, respectively.