Decomposition of a complete bipartite multigraph into arbitrary cycle sizes

2016/08/19 by Asplund, John, Chaffee, Joe, Hammer, James
#05C51 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.05744

Abstract

In a graph G, let μ_G(xy) denote the number of edges between x and y in G. Let λK_v,u be the graph (V∪ U,E) with |V|=v, |U|=u, and μ_G(xy)=\begincases λamp;if x∈ U and y∈ V or if x∈ V and y∈ U
0 amp;otherwise.
\endcases Let M be a sequence of non-negative integers m₁,m₂,…,m_n. An (M)-cycle decomposition of a graph G is a partition of the edge set into cycles of lengths m₁,m₂,…,m_n. In this paper, we establish necessary and sufficient conditions for the existence of an (M)-cycle decomposition of λK_v,u.

Related

• Decompositions of complete multigraphs into cycles of varying lengths
• Decomposing various graphs into short even-length cycles
• Cycle packings of the complete multigraph
• Cyclic cycle systems of the complete multipartite graph
• On the exact decomposition threshold for even cycles