On the packing number of $3$-token graph of the path graph $P_n$

Source abstract

<abstract><p>In 2018, J. M. Gómez et al. showed that the problem of finding the packing number $\rho(F_2(P_n))$ of the 2-token graph $F_2(P_n)$ of the path $P_n$ of length $n\ge 2$ is equivalent to determining the maximum size of a binary code $S'$ of constant weight $w = 2$ that can correct a single adjacent transposition. By determining the exact value of $\rho(F_2(P_n))$, they proved a conjecture of Rob Pratt. In this paper, we study a related problem, which consists of determining the packing number $\rho(F_3(P_n))$ of the graph $F_3(P_n)$. This problem corresponds to the Sloane's problem of finding the maximum size of $S'$ of constant weight $w = 3$ that can correct a single adjacent transposition. Since the maximum packing set problem is computationally equivalent to the maximum independent set problem, which is an NP-hard problem, then no polynomial time algorithms are expected to be found. Nevertheless, we compute the exact value of $\rho(F_3(P_n))$ for $n\leq 12$, and we also present some algorithms that produce a lower bound for $\rho(F_3(P_n))$ with $13\leq n\leq 44$. Finally, we establish an upper bound for $\rho(F_3(P_n))$ with $n\geq 13$.</p></abstract>