N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G into disjoint isomorphic copies of H. An n-sun is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper we have proved that the complete graph of order 2n, K2n can be decomposed into n-2 n-suns, a Hamilton cycle and a perfect matching, when n is even and for odd case, the decomposition is n-1 n-suns and a perfect matching. For an odd order complete graph K2n+1, delete the star subgraph K1, 2n and the resultant graph K2n is decomposed as in the case of even order. The method of building n-suns uses Walecki's construction for the Hamilton decomposition of complete graphs. A spanning tree decomposition of even order complete graphs is also discussed using the labeling scheme of n-sun decomposition. A complete bipartite graph Kn, n can be decomposed into n/2 n-suns when n/2 is even. When n/2 is odd, Kn, n can be decomposed into (n-2)/2 n-suns and a Hamilton cycle.

Keywords: Hamilton cycle, n-sun decomposition, perfectmatching, spanning tree.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057183

References:

[1] W. D. Wallis, ''Magic graphs,'' Birkhauser, 2000.
[2] B. Alspach, J. C. Bermond and Sotteau, ''Decompositions into cycles I: Hamilton decompositions, cycles and rays,'' Kluwer Academic Press 1990, pp. 9-18.
[3] B. Alspach, ''The wonderful Walecki construction,'' 2006, April
[Lecture notes].
[4] B. Alspach and H. Gavlas, ''Cycle decompositioins of Kn and Kn - I,'' J. Combin.. Theory Ser. B, Vol. 81, pp. 77-99, 2001.
[5] D. B. West, ''Introduction to graph theory,'' Pearson Education Pte.Ltd., 2002.
[6] J. L. Gross and J. Yellen, ''Handbook of Graph theory,'' CRC Press, 2004.
[7] R. Laskar and B. Auerbach, ''On decomposition of r-partite graphs into edge-disjoint Hamilton circuits'', Discrete Math. Vol. 14, pp. 265-268, 1976.