Embedding an Edge-colored $K(a^{(p)};\lambda ,\mu )$ into a Hamiltonian Decomposition of $K(a^{(p+r)};\lambda ,\mu )$

Abstract

Let $K(a^{(p)};\lambda ,\mu )$ be a graph with $p$ parts, each part having size $a$, in which the multiplicity of each pair of vertices in the same part (in different parts) is $\lambda$ ($\mu$, respectively). In this paper we consider the following embedding problem: When can a graph decomposition of $K(a^{(p)};\lambda ,\mu )$ be extended to a Hamiltonian decomposition of $K(a^{(p+r)};\lambda ,\mu )$ for $r>0$? A general result is proved, which is then used to solve the embedding problem for all $r\ge \frac{\lambda }{\mu a}+\frac{p-1}{a-1}$. The problem is also solved when $r$ is as small as possible in two different senses, namely when $r=1$ and when $r=\frac{\lambda }{\mu a}-p+1$.

10 pages, 2 figures

References in corpus (1)

• Multiply Balanced Edge Colorings of Multigraphs