Token graphs of stars

Abstract

The $k$-token graph $F_k(G)$ of a graph $G$ has as vertices the $k$-subsets of $V(G)$, two of them being adjacent when their symmetric difference is an edge of $G$. Let $S_n$ be the star with $n$ leaves. Since every edge of $S_n$ is incident with the center, $F_k(S_n)$ is the inclusion graph of the $(k-1)$- and the $k$-subsets of the leaves. We use this identification to determine its diameter, radius, girth, Wiener index and number of spanning trees, and to decompose $F_k(S_{n+1})$ into $F_k(S_n)$ and $F_{k-1}(S_n)$ joined by a matching; the parameters of $F_k(S_n)$ that are already known, such as its connectivity, independence number, automorphism group and spectrum, are collected in an appendix. The two parameters that the identification does not settle are the domination and the packing numbers. For the domination number we prove, for fixed $k\ge 3$, that $(1-\frac{k-2}{k-1}{\pi }_k-o(1))\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)\le \gamma (F_k(S_n))\le (1-\frac{1}{2}(\frac{k-2}{k-1}{)}^{k-2}+o(1))(\genfrac{}{}{0ex}{}{n}{k-1})$, where ${\pi }_k$ is the Turan density of the complete $(k-1)$-uniform hypergraph on $k$ vertices; for $k=3$ both constants are equal to $\frac{3}{4}$, so that $\gamma (F_3(S_n))=(\frac{3}{4}+o(1))\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, and the upper bound takes the exact form $\gamma (F_3(S_n))\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)-\lfloor (n+1{)}^2/8\rfloor$, which is attained for all $3\le n\le 10$. For $k=4$ we improve the upper bound to $(\frac{17}{27}+o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$, which matches the lower bound if Turan's conjecture ${\pi }_4=\frac{5}{9}$ holds. We show that the packing number of $F_k(S_n)$ equals the maximum size $A(n+1,4,k)$ of a binary constant-weight code, and we characterize when the packing and the domination numbers coincide, namely, for $2\le k\le n-1$, exactly when $n=2k-1$ and a Steiner system $S(k-2,k-1,2k-1)$ exists; in that case both parameters equal the Catalan number $C_k$.

arXiv comment42 pages, 3 figures