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

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.

Authors:

• R. Anitha
• R. S. Lekshmi

Keywords:

• Decomposition
• Hamilton cycle
• n-sun graph
• perfect matching
• spanning tree.

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.