Maximal Configurations of Stars

Hung-Lin Fu1, Kuo-Ching Huang1, Chin-Lin Shue1
1Department of Applied Mathematics National Chiao Tung University Hsin-Chu, Taiwan REPUBLIC OF CHINA

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.