# 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. Decompositions of generalized complete graphs Bulletin of The Australian Mathematical Society   Check publisher's open access policy 0004-97271755-1633 2009-12 Article (original research) 10.1017/S0004972709000793 80 3 523 525 3 Cambridge, U.K. Cambridge University Press eng 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). Graph decompositionk-CycleGeneralized complete graphCycle decompositions C1 Provisional Code UQ

 Document type: Journal Article Article (original research) School of Mathematics and Physics

 Versions Version Filter Type Sun, 03 Jan 2010, 00:04:37 EST Thu, 09 Jun 2011, 19:02:29 EST Tue, 20 Sep 2011, 12:20:44 EST Sat, 06 Jul 2013, 10:32:27 EST Tue, 30 Sep 2014, 17:43:26 EST Filtered Full
Citation counts: Cited 0 times in Thomson Reuters Web of Science Article Cited 0 times in Scopus Article Search Google Scholar Sun, 03 Jan 2010, 00:04:37 EST