Decompositions of generalized complete graphs

Smith, Benjamin R. (2009) Decompositions of generalized complete graphs. Bulletin of The Australian Mathematical Society, 80 3: 523-525. doi:10.1017/S0004972709000793

Author Smith, Benjamin R.
Title Decompositions of generalized complete graphs
Journal name Bulletin of The Australian Mathematical Society   Check publisher's open access policy
ISSN 0004-9727
Publication date 2009-12
Sub-type Article (original research)
DOI 10.1017/S0004972709000793
Volume 80
Issue 3
Start page 523
End page 525
Total pages 3
Place of publication Cambridge, U.K.
Publisher Cambridge University Press
Language eng
Formatted abstract
A decomposition of a graph G is a collection of edge-disjoint subgraphs of G whose edges partition the edges of G. In the case where each of these subgraphs is isomorphic to some graph H, we say that G admits a decomposition into H. The problem of determining whether a given graph G admits a decomposition into a given graph H is the primary focus of this thesis. In particular, we are concerned with those cases in which H is a cycle.

Obvious necessary conditions for a graph G (having nonempty edge set) to admit a decomposition into cycles of length k are that: (i) G contains at least k vertices; (ii) every vertex in G has even degree; and (iii) the total number of edges in G is a multiple of the cycle length k. Recent papers by Alspach and Gavlas and Šajna have shown that these three necessary conditions are sufficient in the case where G is either K2𝑛+1 (the complete graph of odd order), or K2𝑛F (the complete graph of even order minus a 1-factor). In this thesis we examine whether conditions (i), (ii) and (iii) above are also sufficient when G is one of λK𝑛 (the λ-fold complete multigraph), K𝑛K𝑚 (the complete equipartite graph having 𝑛 parts of size 𝑚 ) or λK𝑛K𝑚 (the λ-fold complete equipartite graph).
Keyword Graph decomposition
Generalized complete graph
Cycle decompositions
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Sun, 03 Jan 2010, 00:04:37 EST