\(N\)-sun decomposition of complete, complete bipartite and some Harary graphs. (English) Zbl 1186.05094

Anitha, R.; Lekshmi, R. S.

Int. J. Comput. Math. Sci. 2, No. 1, 33-38 (2008).

Summary: 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 \(C_n\) 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 \(K_{2n}\), complete bipartite graph \(K_{2n,2n}\) and the Harary graph \(H_{4,2n}\) have \(n\)-sun decompositions. A labeling scheme is used to construct the \(n\)-suns.

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

decomposition; Hamilton cycle; perfect matching; spanning tree