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

Christophe Ndjatchi; Joel Alejandro Escareño Fernández; L. M. Ríos-Castro; Teodoro Ibarra-Pérez; Hans Christian Correa-Aguado; Hugo Pineda Martínez; Christophe Ndjatchi; Joel Alejandro Escareño Fernández; L. M. Ríos-Castro; Teodoro Ibarra-Pérez; Hans Christian Correa-Aguado; Hugo Pineda Martínez

doi:10.3934/math.2024571

AIMS Mathematics

2024, Volume 9, Issue 5: 11644-11659. doi: 10.3934/math.2024571

Previous Article Next Article

Research article Special Issues

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

1.
Academia de Físico-Matemáticas, Instituto Politécnico Nacional, UPIIZ, P. C. 098160, Zacatecas, México
2.
Ingeniería Mecatrónica, Becario BEIFI-IPN, Instituto Politécnico Nacional, UPIIZ, P. C. 098160, Zacatecas, México
3.
Academia de Físico-Matemáticas, Instituto Politécnico Nacional, CECYT18, Zacatecas, P. C. 098160, Zacatecas, México
4.
Academia de Ingeniería, Instituto Politécnico Nacional, UPIIZ, P. C. 098160, Zacatecas, México
5.
Unidad Académica de Ingenieria Eléctrica, Universidad Autónoma de Zacatecas, Zacatecas, México

Received: 31 January 2024 Revised: 08 March 2024 Accepted: 12 March 2024 Published: 26 March 2024
MSC : 05C10, 05C45

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 $.
- packing number,
- $ 3 $-token graphs,
- error correcting codes,
- binary codes,
- algorithms
Citation: Christophe Ndjatchi, Joel Alejandro Escareño Fernández, L. M. Ríos-Castro, Teodoro Ibarra-Pérez, Hans Christian Correa-Aguado, Hugo Pineda Martínez. On the packing number of $ 3 $-token graph of the path graph $ P_n $[J]. AIMS Mathematics, 2024, 9(5): 11644-11659. doi: 10.3934/math.2024571

Related Papers:

Abstract

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 $.

References

[1]	A. Alzaga, I. Rodrigo, R. Pignol, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, J. Comb. Theory B, 100 (2010), 671–682. https://doi.org/10.1016/j.jctb.2010.07.001 doi: 10.1016/j.jctb.2010.07.001
[2]	S. Butenko, P. Pardalos, I. Sergienko, V. Shylo, P. Stetsyuk, Estimating the size of correcting codes using extremal graph problems, In: Optimization, New York: Springer, 2009,227–243. https://doi.org/10.1007/978-0-387-98096-6_12
[3]	W. Carballosa, R. Fabila-Monroy, J. Leaños, L. M. Rivera, Regularity and planarity of token graphs, Discuss. Math. Graph T., 37 (2017), 573–586. https://doi.org/10.7151/dmgt.1959 doi: 10.7151/dmgt.1959
[4]	H. de Alba, W. Carballosa, J. Leaños, L. M. Rivera, Independence and matching numbers of some token graphs, Australas. J. Comb., 76 (2016), 387–403.
[5]	J. A. Escareño Fernández, C. Ndjatchi, L. M. Ríos-Castro, Algorithms-for-packing-number-of-3-token, 2024. Available from: https://github.com/TheAlexz/Algorithms-for-packing-number-of-3-token.
[6]	R. Fabila-Monroy, D. Flores Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, D. R. Wood, Token graphs, Graphs and Combinatorics, 28 (2012), 365–380. https://doi.org/10.1007/s00373-011-1055-9 doi: 10.1007/s00373-011-1055-9
[7]	R. Fabila-Monroy, J. Leaños, A. L. Trujillo-Negrete, On the connectivity of token graphs of trees, Discrete Math. Theor., 24 (2022), 1–23. https://doi.org/10.46298/dmtcs.7538 doi: 10.46298/dmtcs.7538
[8]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, New York: W. H. Freeman, 1979.
[9]	Google Docs, Algorithms for computing the lower and upper bounds for the packing number of $3$-token graph of path graph. Available from: http://tinyurl.com/25bx8dpe.
[10]	A. S. Hassan, A generalisation of Johnson graphs with an application to triple factorisations, Discrete Math., 338 (2015), 2026–2036. https://doi.org/10.1016/j.disc.2015.05.001 doi: 10.1016/j.disc.2015.05.001
[11]	D. S. Hochbaum, D. B. Shmoys, A best possible heuristic for the $k$-center problem, Math. Oper. Res., 10 (1985), 175–366. https://doi.org/10.1287/moor.10.2.180 doi: 10.1287/moor.10.2.180
[12]	J. Leaños, C. Ndjatchi, The edge-cdonnectivity of Token Graphs, Graph. Combinator., 37 (2021), 1013–1023. https://doi.org/10.1007/s00373-021-02301-0 doi: 10.1007/s00373-021-02301-0
[13]	J. Leaños, A. L. Trujillo-Negrete, The connectivity of token graphs, Graph. Combinator., 34 (2018), 777–790. https://doi.org/10.1007/s00373-018-1913-9 doi: 10.1007/s00373-018-1913-9
[14]	K. G. Mirajkar, Y. B. Priyanka, Traversability and covering invariants of token graphs, International J. Math. Combin., 2 (2016), 132–138.
[15]	L. M. Riós-Castro, Números de dominación y empaquetamiento de ciertas gráficas de fichas, PhD Thesis, Universidad Autónoma de Zacatecas, 2018.
[16]	G. Rossum, Python tutorial, Netherlands: CWI (Centre for Mathematics and Computer Science), 1995. Available from: https://dl.acm.org/doi/10.5555/869378
[17]	N. J. A. Sloane, On single-deletion-correcting codes, 2002, arXiv: math/0207197. https://doi.org/10.48550/arXiv.math/0207197
[18]	N. J. A. Sloane, A085680-OEIS. Available from: https://oeis.org/A085680.
[19]	J. M. G. Soto, J. Leaños, L. M. Ríos-Castro, L. M. Rivera, The packing number of the double vertex graph of the path graph, Discrete Appl. Math., 247 (2018), 327–340. https://doi.org/10.1016/j.dam.2018.03.085 doi: 10.1016/j.dam.2018.03.085
[20]	Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL, 2019. Available from: https://www.wolfram.com/mathematica/

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)