@article{Ndjatchi2024, 
author = {Christophe Ndjatchi and Joel Alejandro Escareño Fernández and L. M. Ríos-Castro and Teodoro Ibarra-Pérez and Hans Christian Correa-Aguado and Hugo Pineda Martínez},
title = {On the packing number of    3-token graph of the path graph        P    n},
year = {2024},
journal = {AIMS Mathematics},
volume = {9},
number = {5},
pages = {11644-11659},
keywords = {packing number, 3-token graphs, error correcting codes, binary codes, algorithms},
url = {https://www.sciopen.com/article/10.3934/math.2024571},
doi = {10.3934/math.2024571},
abstract = {In 2018, J. M. Gómez et al. showed that the problem of finding the packing number    ρ  (      F    2    (      P    n    )  ) of the 2-token graph        F    2    (      P    n    ) of the path        P    n   of length    n  ≥  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    ρ  (      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    ρ  (      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    ρ  (      F    3    (      P    n    )  ) for    n  ≤  12, and we also present some algorithms that produce a lower bound for    ρ  (      F    3    (      P    n    )  ) with    13  ≤  n  ≤  44. Finally, we establish an upper bound for    ρ  (      F    3    (      P    n    )  ) with    n  ≥  13.}
}