Decomposition of complete multigraphs into stars

✍ Scribed by Michael Tarsi

• Publisher: Elsevier Science
• Year: 1979
• Tongue: English
• Weight: 531 KB
• Volume: 26
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(79)90034-7

✦ Synopsis

A necessary and sufficient condition for the existence of a decomposition of A&, irto stars is given. A complete multigraph AK, is a complete graph & in which every edge is taken A times. A complete multigraph A&, is said to have a G-decomposition G[h, v] if it is a union of edge disjoint subgraphs of &, each of them isomorphic to a fixed graph G. The basic problem conriected with the G-decomposition is to determine, for a given graph G, the necessary and sufficient conditions 011 A and v for the existence of a decomposition G[A, v]. When the graph G is itself a complete graph Kk, then the decomposition &[A, v] is known as a balanced incomplete block design (BIBID): B[k, A; v], [3]. Only relatively recently other graphs than Kk have been considered. A survey of results in this direction and a description of methods used, may be found in [l].

In this paper we consider the case where G is an m-star S,,,, m-star being a complete bipartite graph K1,,. The vertex of degree m in S,,, is called the centre of the star and the m vertices of degree 1 are called the terminal vertices of the star.

The object of this paper is to CGterrnine the necessary and sufficient condition on A and v for the existence of decomposition &, [A, v] of AK,, into edge disjoint stars Sm. Several special cases of this problem were considered already by other authors. Especially should be mentioned the result by Huang [4], who solved completely the case A = 1. Now we state our main result? heorem. The necessary and suficient condition for the existence of a deco;,position Sm [A, v] is that (1.1) AV(V -1) =O (mod 2m)