(4, 5)-cycle systems of complete multipartite graphs

Ming Hway Huang, Hung-Lin Fu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)999-1006
Number of pages8
JournalTaiwanese Journal of Mathematics
Volume16
Issue number3
DOIs
StatePublished - 1 Jan 2012

Keywords

  • Alspach conjecture
  • Cycle decomposition
  • Cycle system

Fingerprint Dive into the research topics of '(4, 5)-cycle systems of complete multipartite graphs'. Together they form a unique fingerprint.

Cite this