Exponential growth rate of the minimum order of a complete graph decomposable into factors of given star number

For integers $n \ge 2$ and $k \ge 2$, let $f(n,k)$ be the smallest $m \ge n$ such that the edge set of the complete graph $K_m$ decomposes into $k$ edge-disjoint spanning factors each of star number $n$, where a graph has star number $n$ when every set of $n$ of its vertices is contained in the vertex set of some star subgraph (a star is a graph $K_{1,r}$, one center vertex joined to $r$ leaves). Erdős, Sauer, Schaer, and Spencer introduced this parameter in 1975 and proved that $f(n,k)$ grows exponentially in $n$ and linearly in $k$: a probabilistic two-coloring argument gives $f(n,k) \le c\,n^2 2^n k$, while a counting recursion gives $f(n,k) \ge \tfrac{1}{2}(3/2)^n k$. Determining the exponential growth rate of $f(n,k)$ in $n$ — in particular, whether the base 2 in the upper bound is essentially sharp, or whether $f(n,k) \le C(2-\varepsilon)^n k$ for some $\varepsilon > 0$ — remains open for every $n \ge 3$. The case $n = 2$ coincides with the classical problem of decomposing complete graphs into factors of diameter at most 2, which later work substantially resolved; the general case has lain dormant since 1975.

Background

A decomposition (or factorization) of a graph into $k$ factors is a partition of its edge set into $k$ spanning subgraphs, that is, subgraphs that contain every vertex of the host graph. A classical line of extremal graph theory studied decompositions of complete graphs (the graph $K_m$ on $m$ vertices, every pair joined by an edge) into factors of small diameter, where the diameter of a graph is the largest, over all pairs of vertices, of the length of a shortest path between the pair. Writing $f(k)$ for the smallest $m$ such that $K_m$ decomposes into $k$ factors of diameter at most 2, elementary examples give $f(2) = 5$: the ten edges of $K_5$ split into two 5-cycles, each of diameter 2. Sauer, and Sauer and Schaer, began the systematic study of $f(k)$, and Bosák continued it; the resulting Bollobás–Bosák conjecture that $f(k) = 6k$ was confirmed for all sufficiently large $k$ by Znám in 1982. Marková refined the small cases (showing $f(7) \ge 34$), Stacho and Urland proved that $K_{12}$ does not decompose into three diameter-2 factors, settling the exact value for $k = 3$, and Vukičević studied mixed decompositions into factors of diameter two and three.

In 1975 Erdős, Sauer, Schaer, and Spencer generalized this question from pairs of vertices to arbitrary $n$-tuples. Call a star any graph isomorphic to $K_{1,r}$, one center vertex joined to $r$ leaves, and say that a graph has star number $n$ if every set of $n$ of its vertices is contained in the vertex set of some star subgraph. For $n = 2$ this says exactly that every pair of vertices is adjacent or has a common neighbor, which is the statement that the graph has diameter at most 2; so the new notion extends the diameter-2 condition. Define $f(n,k)$ as the smallest $m \ge n$ such that $K_m$ decomposes into $k$ factors of star number $n$; thus $f(2,k)$ recovers the diameter-2 function $f(k)$ above, and $f(2,2) = 5$.

The 1975 paper determined $f(n,k)$ up to an exponential gap in $n$. For the upper bound the authors proved a probabilistic lemma: for $\nu > c\,n^2 2^n$, with $c$ an absolute constant, the edges of the complete bipartite graph $K_{\nu,\nu}$ (two parts of $\nu$ vertices each, every cross pair joined) admit a two-coloring such that for all subsets $C$ and $D$ of the two parts with $|C| + |D| \le n$, some index $t$ has the $t$-th vertex of the first part joined to all of $D$ in the first color and the $t$-th vertex of the second part joined to all of $C$ in the second color; the proof colors randomly and applies a union-bound estimate, summing the failure probabilities of all bad events. Using one such bipartite template between every pair of $k$ vertex classes of size $\nu$, and coloring the edges inside each class by the class, yields a decomposition of $K_{k\nu}$ into $k$ factors of star number $n$: given any $n$ vertices, the coupled covering property supplies, in each color, a center joined to all of them. Hence $f(n,k) \le c\,n^2 2^n k$, and absorbing the polynomial prefactor, $f(n,k) \le c_1(\varepsilon)(2+\varepsilon)^n k$ for every fixed $\varepsilon > 0$. For the lower bound, a double-counting argument — each factor must place every $n$-set of vertices within the neighborhood of some single vertex, which forces many vertices of high degree in each color — combined with a recursion obtained by restricting a decomposition to a well-chosen vertex subset that carries a decomposition with star number reduced by one, gives $f(n,k) \ge \tfrac{1}{2}(3/2)^n k$, via the recursion $f(n,k) \ge \tfrac{3}{2} f(n-1,k) - 1$ with base $f(2,k) \ge 2k+1$.

A caution on terminology: later literature uses the phrase star number in a different sense. Lin and Shyu defined the star number of a complete multigraph as the minimum number of stars needed to cover its edge set, a quantity related to star arboricity (the minimum number of star forests, forests whose components are all stars, that cover the edges); that notion is unrelated to the vertex-covering property studied here.

Problem Statement

Determine the exponential growth rate in $n$ of $f(n,k)$, the smallest $m \ge n$ such that $K_m$ decomposes into $k$ edge-disjoint spanning factors each of star number $n$ (every $n$ vertices of the factor are contained in the vertex set of one of its stars), for $n \ge 3$ and $k \ge 2$. Up to polynomial prefactors and absolute constants, the known bounds pin the exponential base only to the interval $[3/2, 2]$: from above, $f(n,k) \le c\,n^2 2^n k$; from below, $f(n,k) \ge \tfrac{1}{2}(3/2)^n k$. The core questions are: (1) is the base 2 essentially sharp — for instance, does $f(n,k) \ge c'\,2^n k / \mathrm{poly}(n)$ hold — or does there exist $\varepsilon > 0$ with $f(n,k) \le C(2-\varepsilon)^n k$? (2) More generally, determine or narrow the exponential rate from either side; if the limit $\rho = \lim_{n \to \infty} \big( \inf_{k \ge 2} f(n,k)/k \big)^{1/n}$ exists, decide whether $\rho = 2$ or $\rho < 2$. Determining the exponential growth rate here means deciding the dichotomy posed in (1) and (2), namely whether the base is $2$ or strictly below $2$ (equivalently, whether $\rho = 2$ or $\rho < 2$); either branch of (1) already settles it, an upper bound $f(n,k) \le C(2-\varepsilon)^n k$ for some $\varepsilon > 0$ placing the base strictly below $2$ and a lower bound $f(n,k) \ge c'\,2^n k / \mathrm{poly}(n)$ forcing $\rho = 2$. The two branches are not exhaustive — a rate intermediate between them, such as $f(n,k) = 2^n k / n^{\log n}$, satisfies neither even though its base is $2$. By contrast, narrowing the interval only from below, with a lower bound whose base lies above $3/2$ but still below $2$, leaves the dichotomy undecided. The case $n = 2$ is excluded from the open core because it coincides with the diameter-2 factorization problem, for which later literature established $f(2,k) = 6k$ for all sufficiently large $k$ and settled the small cases.

References

1. Paul Erdős, Norbert Sauer, Jonathan Schaer, Joel Spencer, 'Factorizing the complete graph into factors with large star number', Journal of Combinatorial Theory, Series B 18(2):180-183, 1975. DOI: 10.1016/0095-8956(75)90046-5, https://doi.org/10.1016/0095-8956(75)90046-5 (Open-access scan: https://www.renyi.hu/~p_erdos/1975-15.pdf; zbMATH review Zbl 0279.05122, https://zbmath.org/0279.05122)
2. Norbert Sauer, 'On the factorisation of the complete graph into factors of diameter 2', Journal of Combinatorial Theory 9:423-426, 1970. DOI: 10.1016/S0021-9800(70)80096-5, https://doi.org/10.1016/S0021-9800(70)80096-5
3. Norbert Sauer, J. Schaer, 'On the factorization of the complete graph', Journal of Combinatorial Theory, Series B 14:1-6, 1973. DOI: 10.1016/S0095-8956(73)80003-6, https://doi.org/10.1016/S0095-8956(73)80003-6
4. Juraj Bosák, 'Disjoint factors of diameter two in complete graphs', Journal of Combinatorial Theory, Series B 16:57-63, 1974. DOI: 10.1016/0095-8956(74)90095-1, https://doi.org/10.1016/0095-8956(74)90095-1
5. Štefan Znám, 'On a conjecture of Bollobás and Bosák', Journal of Graph Theory 6:139-146, 1982. DOI: 10.1002/jgt.3190060208, https://doi.org/10.1002/jgt.3190060208
6. Iveta Marková, 'Decomposition of complete graphs into factors with diameter two', Acta Mathematica Universitatis Comenianae 56-57:235-241, 1990. zbMATH: 0759.05073, https://zbmath.org/0759.05073
7. Ladislav Stacho, Erik Urland, 'The nonexistence of a decomposition of complete graph $K_{12}$ into three factors with diameter two', Journal of Combinatorial Mathematics and Combinatorial Computing 21:147-159, 1996. zbMATH: 0861.05048, https://zbmath.org/0861.05048
8. Damir Vukičević, 'Decomposition of complete graphs into factors of diameter two and three', Discussiones Mathematicae Graph Theory 23(1):37-54, 2003. DOI: 10.7151/dmgt.1184, https://doi.org/10.7151/dmgt.1184
9. Shinsei Tazawa, 'Claw-decomposition and evenly-partite-claw-decomposition of complete multipartite graphs', Hiroshima Mathematical Journal 9:503-531, 1979. DOI: 10.32917/hmj/1206134898, https://doi.org/10.32917/hmj/1206134898
10. Ján Plesník, 'Complexity of decomposing graphs into factors with given diameters or radii', Mathematica Slovaca 32(4):379-388, 1982. Open-access full text at DML-CZ: https://dml.cz/handle/10338.dmlcz/136306 (PDF: https://dml.cz/bitstream/handle/10338.dmlcz/136306/MathSlov_32-1982-4_9.pdf)
11. Chiang Lin, Tay-Woei Shyu, 'Star number and star arboricity of a complete multigraph', Czechoslovak Mathematical Journal 56(3):961-967, 2006. DOI: 10.1007/s10587-006-0071-z, https://doi.org/10.1007/s10587-006-0071-z
12. Michael D. Plummer, 'Graph factors and factorization: 1985-2003: A survey', Discrete Mathematics 307:791-821, 2007. DOI: 10.1016/j.disc.2005.11.059, https://doi.org/10.1016/j.disc.2005.11.059