Enclosings of decompositions of complete multigraphs in 2-factorizations

Feghali, Carl; Johnson, Matthew

Abstract

Let k, m, n, λ, and μ be positive integers. A decomposition of math formula into edge-disjoint subgraphs math formula is said to be enclosed by a decomposition of math formula into edge-disjoint subgraphs math formula if math formula and, after a suitable labeling of the vertices in both graphs, math formula is a subgraph of math formula and math formula is a subgraph of math formula for all math formula. In this paper, we continue the study of enclosings of given decompositions by decompositions that consist of spanning subgraphs. A decomposition of a graph is a 2-factorization if each subgraph is 2-regular and spanning, and is Hamiltonian if each subgraph is a Hamiltonian cycle. We give necessary and sufficient conditions for the existence of a 2-factorization of math formula that encloses a given decomposition of math formula whenever math formula and math formula. We also give necessary and sufficient conditions for the existence of a Hamiltonian decomposition of math formula that encloses a given decomposition of math formula whenever math formula and either math formula or math formula and math formula, or math formula, math formula, and math formula.

Citation

Feghali, C., & Johnson, M. (2018). Enclosings of decompositions of complete multigraphs in 2-factorizations. Journal of Combinatorial Designs, 26(5), 205-218. https://doi.org/10.1002/jcd.21601

• Journal Article Type: Article
• Acceptance Date: Jan 1, 2018
• Online Publication Date: Jan 18, 2018
• Publication Date: May 1, 2018
• Deposit Date: Mar 15, 2018
• Publicly Available Date: Jan 18, 2019
• Journal: Journal of Combinatorial Designs
• Print ISSN: 1063-8539
• Electronic ISSN: 1520-6610
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 26
• Issue: 5
• Pages: 205-218
• DOI: https://doi.org/10.1002/jcd.21601
• Public URL: https://durham-repository.worktribe.com/output/1365065