Maximal Configurations of Stars

Abstract

A star $S_q$, with $q$ edges, is a complete bipartite graph $K_{1,q}$. Two figures of the complete graph $K_n$ on a given set of $k$ vertices are compatible if they are edge-disjoint, and a configuration is a set of pairwise compatible figures. In this paper, we take stars as our figures. A configuration $C$ is said to be maximal if there is no figure (star) $f\notin C$ such that $\{f\}\cup C$ is also a configuration. The size of a configuration $F$, denoted by $|F|$, is the number of its figures. Let $\text{Spec}(n,q)$ (or simply $\text{Spec}(n)$) denote the set of all sizes such that there exists a maximal configuration of stars with this size. In this paper, we completely determine $\text{Spec}(n)$, the spectrum of maximal configurations of stars. As a special case, when $n$ is an order of a star system, we obtain the spectrum of maximal partial star systems.