Publications
Sort:
Open Access Research Article Issue
On the packing number of 3-token graph of the path graph P n
AIMS Mathematics 2024, 9(5): 11644-11659
Published: 15 May 2024
Abstract PDF (409.7 KB) Collect
Downloads:0

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.

Total 1