Embedding an edge‐coloring of K(nr;λ1,λ2) into a Hamiltonian decomposition of K(nr+2;λ1,λ2)

Abstract

AbstractThis paper focuses on graph decompositions of , the ‐partite multigraph in which each part has size , where two vertices in the same part or different parts are joined by exactly edges or edges respectively. Assuming one condition, necessary and sufficient conditions are found to embed a k‐edge‐coloring of into a Hamiltonian decomposition of . In the tightest case, this assumption is in fact proved to be a new necessary condition. Unlike previous results, of particular interest here is a necessary condition involving the existence of certain components in a related bipartite graph.