N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. A decomposition of a graph G is a partition of its edge set. An n-sun graph is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper, we define n-sun decomposition of some even order graphs with a perfect matching. We have proved that the complete graph K2n, complete bipartite graph K2n, 2n and the Harary graph H4, 2n have n-sun decompositions. A labeling scheme is used to construct the n-suns.

Keywords: Decomposition, Hamilton cycle, n-sun graph, perfect matching, spanning tree.

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

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.