DECOMPOSITIONS OF $K_{m,n}$ INTO 4-CYCLES AND 8-CYCLES
Main Article Content
Abstract
In this paper it is shown that $G$ can be decomposed into $p$ copies of $C_4$ and $q$ copies of $C_8$ for each pair of nonnegative integers $p$ and $q$ which 8atisfics the equation $4p+ Sq = |E(G)|$, where $E(G)$ is the number of_edges of $G$, when
(1) $G = K_{m, n}$ the complete bigartite graph, if $m$ and $n$ are even,
(2) $G = K_{m, n}-F$, $K_{m, n}$ with 1-factor removed, if $m = n \equiv 1$ (mod 4), and
(3) $G = K_{m, n}-(F \cup C_6)$, $K_{m, n}$,with 1-factor and one 6-cycle removed, if $m = n \equiv 3$ (mod 4).
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
References
D. E. Dryanl and P, Adams, "Decomposing the complete graph into cycles of many lengths," Graphs Combin., 11(1995), 97-102
K. Heinrich, P. Horak and A. Rosa, "On Alspach's conjecture," Discrete Math. 77(1989), 97-121.
K. Heinrich and G. Nonay, "Exact coverings of 2-paths by 4-cyclcs," J. Combin. Theory Ser. (A), 45(1987), 50-61.
J. L. Ramirez-Alfonsin, "Cycle decompositions of complete and complete multipartite Graph," Australas. J. Combin., 11(1995), 233-238.
Sotteau, "Decomposition of $K_{m,n}( K_{m,n}*)$ into cycles (Circuits) of length $2k$," J. Combin. Theory Ser. (B), 30(1981), 75-81.