TY - JOUR
T1 - (4, 5)-cycle systems of complete multipartite graphs
AU - Huang, Ming Hway
AU - Fu, Hung-Lin
PY - 2012
Y1 - 2012
N2 - In 1981, Alspach conjectured that if 3 ≤ mi ≤ v, v is odd and v(v-1)/2 = m1+m2+···+mt, then the complete graph Kv can be decomposed into t cycles of lengths m1,m2,···,mt respectively; if v is even, v(v-2)/2 = m1+m2+···+mn, then the complete graph minus a one-factor Kv - F can be decomposed into t cycles of lengths m1,m2,···,mn respectively. In this paper, we extend the study to the decomposition of the complete equipartite graph Km(n). For mi ∈ {4, 5}, we prove that the trivial necessary conditions are also sufficient.
AB - In 1981, Alspach conjectured that if 3 ≤ mi ≤ v, v is odd and v(v-1)/2 = m1+m2+···+mt, then the complete graph Kv can be decomposed into t cycles of lengths m1,m2,···,mt respectively; if v is even, v(v-2)/2 = m1+m2+···+mn, then the complete graph minus a one-factor Kv - F can be decomposed into t cycles of lengths m1,m2,···,mn respectively. In this paper, we extend the study to the decomposition of the complete equipartite graph Km(n). For mi ∈ {4, 5}, we prove that the trivial necessary conditions are also sufficient.
KW - Alspach conjecture
KW - Cycle decomposition
KW - Cycle system
UR - http://www.scopus.com/inward/record.url?scp=84861133414&partnerID=8YFLogxK
U2 - 10.11650/twjm/1500406672
DO - 10.11650/twjm/1500406672
M3 - Article
AN - SCOPUS:84861133414
SN - 1027-5487
VL - 16
SP - 999
EP - 1006
JO - Taiwanese Journal of Mathematics
JF - Taiwanese Journal of Mathematics
IS - 3
ER -