Embedding an edge-coloring of K(nr;λ<inf>1</inf>,λ<inf>2</inf>) into a Hamiltonian decomposition of K(nr+2;λ<inf>1</inf>,λ<inf>2</inf>)

Abstract

This paper focuses on graph decompositions of (Formula presented.), the (Formula presented.) -partite multigraph in which each part has size (Formula presented.), where two vertices in the same part or different parts are joined by exactly (Formula presented.) edges or (Formula presented.) edges respectively. Assuming one condition, necessary and sufficient conditions are found to embed a k-edge-coloring of (Formula presented.) into a Hamiltonian decomposition of (Formula presented.). 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.