Premium
Maximal sets of hamilton cycles in complete multipartite graphs
Author(s) -
Daven Mike,
MacDougall J. A.,
Rodger C. A.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10096
Subject(s) - combinatorics , mathematics , multipartite , cograph , bipartite graph , discrete mathematics , pancyclic graph , complete graph , disjoint sets , 1 planar graph , graph , chordal graph , physics , quantum mechanics , quantum entanglement , quantum
A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G − E ( H ) contains no hamilton cycles. In this context, the spectrum S ( G ) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003