Stars and Hyperstars

Abstract

A \textit{$k$-star} is a complete bipartite graph $K_{1,k}$, and a hypergraph $G=(X,\mathcal{E})$ is a \textit{hyperstar} with center $C$ if $\displaystyle C\subseteq\bigcap_{E\in\mathcal{E}}E$. Given (hyper)graphs $G$ and $H$, an $H$-decomposition of $G$ is a partition of the edges of $G$ into copies of $H$. In this work, we investigate different decomposition-like properties of stars and hyperstars. We discuss maximum packings of $\lambda K_{n}$ with $k$-stars, embeddings of partial $k$-star decompositions of $K_{n}$, and decompositions of complete hypergraphs and complete uniform hypergraphs into hyperstars with center-size 1.

We characterize the number of edges in a maximum packing of $\lambda K_{n}$ with $k$-stars for the cases $\lambda=1$ for any $n$, and $\lambda>1$ for $n\geq 2k$. For the case where $\lambda>1$ with $n<2k$ we give partial results. Our main result for an embedding of a partial $k$-star decomposition of $K_{n}$ is a small embedding in which the number of new vertices depends only on $k$. The question of decomposing both complete hypergraphs and complete uniform hypergraphs into hyperstars has already been solved by Lonc \cite{Lonc1}, but we give an alternative proof.