Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T01:58:57.056Z Has data issue: false hasContentIssue false

Packing Circuits into KN

Published online by Cambridge University Press:  10 December 2001

PAUL BALISTER
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA; (e-mail: balistep@msci.memphis.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We shall pack circuits of arbitrary lengths into the complete graph KN. More precisely, if N is odd and [sum ]ti=1mi = (N2), mi [ges ] 3, then the edges of KN can be written as an edge-disjoint union of circuits of lengths m1,…,mt. Since the degrees of the vertices in any such packing must be even, this result cannot hold for even N. For N even, we prove that if [sum ]ti=1mi [les ] (N2) − N−2 then we can write some subgraph of KN as an edge-disjoint union of circuits of lengths m1,…,mt. In particular, KN minus a 1-factor can be written as a union of such circuits when [sum ]ti=1mi = (N2) − N−2. We shall also show that these results are best possible.

Information

Type
Research Article
Copyright
2001 Cambridge University Press