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

Yizhe Gao, Dan Roberts

Abstract


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.


Keywords


graph pair, decomposition, multidecomposition, packing, covering, cycle, prism

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.10

References

A. Abueida and M. Daven, Multidesigns for Graph-Pairs of Order 4 and 5, Graphs and Com- binatorics (2003) 19, 433–447.

P. Adams, D. Bryant, and M. Buchanan, A Survey on the Existence of G-Designs, J. Combin. Designs 16 (2008), 373–410.

Q. Kang, H.Zhao, and C. Ma, Graph designs for nine graphs with six vertices and ninee dges, Ars Combin. 88 (2008), 379–395.

M. Sˇajna, Cycle decompositions III: Complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 1, 27–78.

D. Sotteau, Decomposition of K_m,n (K*_m,n) into Cycles (Circuits) of Length 2k, J. Combin. Theory Ser. B 30 1981, 75–81.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats