Maximum cyclic 4-cycle packings of the complete multipartite graph

Shung Liang Wu, Hung-Lin Fu*

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A graph G is said to be m-sufficient if m is not exceeding the order of G, each vertex of G is of even degree, and the number of edges in G is a multiple of m. A complete multipartite graph is balanced if each of its partite sets has the same size. In this paper it is proved that the complete multipartite graph G can be decomposed into 4-cycles cyclically if and only if G is balanced and 4-sufficient. Moreover, the problem of finding a maximum cyclic packing of the complete multipartite graph with 4-cycles are also presented.

Original languageEnglish
Pages (from-to)365-382
Number of pages18
JournalJournal of Combinatorial Optimization
Volume14
Issue number2-3
DOIs
StatePublished - 1 Oct 2007

Keywords

  • 4-cycle
  • Complete multipartite graph
  • Cycle packing
  • Cycle system
  • Cyclic

Fingerprint Dive into the research topics of 'Maximum cyclic 4-cycle packings of the complete multipartite graph'. Together they form a unique fingerprint.

  • Cite this