EL EMPAQUETAMIENTO EN GRÁFICAS DE
FICHAS COMO UNA HERRAMIENTA PARA
LA RESOLUCIÓN DE PROBLEMAS EN LA
TEORÍA DE CÓDIGOS CORRECTORES DE
ERRORES
THE PACKING OF TOKEN GRAPHS AS A TOOL FOR
PROBLEM-SOLVING IN ERROR-CORRECTING CODE
THEORY
Luis Manuel Ríos-Castro
Instituto Politécnico Nacional, México
Christophe Ndjatchi
Instituto Politécnico Nacional, UPIIZ, México
Teodoro Ibarra-Pérez
Instituto Politécnico Nacional, UPIIZ, México
pág. 1084
DOI: https://doi.org/10.37811/cl_rcm.v9i3.17700
El Empaquetamiento en Gráficas de Fichas como una Herramienta para la
Resolución de Problemas en la Teoría de Códigos Correctores de Errores
Luis Manuel Ríos-Castro 1
lriosc@ipn.mx
https://orcid.org/0009-0008-9326-1854
Instituto Politécnico Nacional
México
Christophe Ndjatchi
mndjatchi@ipn.mx
https://orcid.org/0000-0003-2702-9981
Instituto Politécnico Nacional, UPIIZ
México
Teodoro Ibarra-Pérez
tibarrap@ipn.mx
https://orcid.org/0000-0001-5220-7001
Instituto Politécnico Nacional, UPIIZ
México
RESUMEN
La teoría de grafos se aplica en muchas áreas de la ciencia, como la computación, la química, las
biociencias, las redes, los sistemas de seguridad y la toma de decisiones en estudios de sistemas de
potencia, convirtiéndose en una herramienta importante en múltiples campos. En este artículo de
divulgación se presenta el estudio de un parámetro particular, conocido como el número de
empaquetamiento, dentro de una familia especial de gráficas denominadas grafos de fichas, además se
muestra cómo este permite abordar y contribuir a la resolución de problemas en la teoría de códigos
correctores de errores.
Palabras clave: teoría de gráficas, gráficas de fichas, códigos correctores
1
Autor principal.
Correspondencia: mndjatchi@ipn.mx
pág. 1085
The Packing of Token Graphs as a Tool for Problem-Solving in Error-
Correcting Code Theory
ABSTRACT
Graph theory is applied in many areas of science, such as computing, chemistry, biosciences, networks,
security systems, and decision-making in power system studies, becoming an important tool in multiple
fields. This expository article presents the study of a particular parameter, known as the packing number,
within a special family of graphs called token graphs. Furthermore, it shows how this parameter allows
us to address and contribute to the solution of problems in the error-correcting codes theory.
Keywords: graph theory, token graphs, error-correcting codes
Artículo recibido 07 abril 2025
Aceptado para publicación: 13 mayo 2025
pág. 1086
INTRODUCCIÓN
La teoría de grafos (también conocida como la teoría de gráficas) nació en 1736 con la resolución por
el matemático Leonhard Euler del problema de los siete puentes de Königsberg (Rusia). Desde entonces,
esta teoría ha tenido muchas aplicaciones en diferentes campos de la ciencia. Por ejemplo, en física, la
teoría de gráficas ofrece un marco matemático riguroso para analizar la conectividad y las propiedades
de transporte en materiales desordenados, donde la noción de caminos y clusters es fundamental
(Stauffer & Aharony, 2018). En ingeniería, esta teoría ha proporcionado un lenguaje y un conjunto de
herramientas para modelar y analizar las relaciones entre objetos, los cuales pueden ser de cualquier
tipo, desde componentes en un circuito electrónico hasta nodos en una red de transporte (Sayeekumar
et al. 2015), entre otras.
Con el aumento en la necesidad de transmisión y almacenamiento de información (datos) en las últimas
décadas, es cada vez más imprescindible contar con métodos que ayuden a mantener no solamente la
seguridad de estos datos sino también su confiabilidad (Castillo et al. 2025). Por ejemplo, al enviar una
fotografía o un mensaje de texto a través de un dispositivo electrónico pueden surgir errores en la
transmisión que distorsionen la imagen o el mensaje original. Para corregir dichos errores ocurridos
durante la transmisión, surgió a mitad del siglo pasado la teoría de códigos correctores de errores, la
cual ha sido impulsada por diferentes ramas de la ciencia como la computación y, desde luego, las
matemáticas. Por ejemplo, el matemático Neil Sloane ha relacionado los códigos correctores con
empaquetamiento de esferas y empaquetamiento en gráficas (Sloane, 2002).
De manera análoga al trabajo de Sloane (Sloane, 2002), en este artículo se explica de forma divulgativa,
cómo con la determinación del número de empaquetamiento denotado por ρ, (es decir, con el hallazgo
del tamaño máximo de un subconjunto de vértices en el que la distancia entre cualquier par de ellos es
estrictamente mayor que 2) en las gráficas denominadas gráficas de fichas (o token graphs) denotadas
por Fk(G) (Fabila-Moroy et al., 2012), se puede corregir un error en un código binario. Es importante
mencionar que este análisis se enfocará especialmente en el número de empaquetamiento de las gráficas
de 3-fichas, denotada por F3(Pn), del grafo camino denotado por Pn (Ndjatchi et al. 2024).
La relevancia de estudiar el número de empaquetamiento en tales gráficas radica en su equivalencia con
problemas de diseño de códigos binarios correctores de errores. En investigaciones previas, (Gómez et
pág. 1087
al., 2018) demostraron que determinar el número de empaquetamiento, ρ(F2(Pn)), de las gráficas de 2-
fichas, F2(Pn), del grafo camino Pn, es equivalente a encontrar el tamaño máximo de un código binario
de peso constante 2 que corrige una única transposición adyacente, el cual se encuentra en la sucesión
A085680 de la The On-Line Encyclopedia of Integer Sequences (OEIS) (Sloane, 2017).
En este contexto, el presente trabajo examina una conexión entre la teoría de gráficas y la teoría de
códigos correctores de errores, a través del estudio de las llamadas gráficas de fichas y el concepto de
número de empaquetamiento.
De forma más precisa, se explora la conexión entre la gráfica de 3-fichas, F3(Pn), del camino Pn, la
determinación del número de empaquetamiento ρ(F3(Pn)) y su relación con el problema de la
determinación del máximo código corrector que puede corregir una única transposición adyacente. Cabe
mencionar que la determinación del número de empaquetamiento ρ(F3(Pn)) es esencial para diseñar
códigos de tamaño máximo que protejan la integridad de la información ante este tipo específico de
errores durante la transmisión o almacenamiento de esta.
METODOLOGÍA
Este artículo se enfoca en un análisis de tipo cualitativo, con un tipo de estudio descriptivo y aplicado
en el área de teoría de gráficas. Su propósito es ilustrar de manera accesible una estructura matemática
mediante una narrativa didáctica, induciendo el acercamiento intuitivo del lector a los conceptos de:
gráfica, gráfica camino, de fichas y códigos correctores. El diseño adoptado es de tipo constructivo, el
cual se centra en la exploración de conceptos a partir de ejemplos visuales y situaciones concretas que
permiten construir significados matemáticos de manera progresiva.
Dado que se propone un estudio teórico sin aplicación directa a una población humana, no se realizó un
muestreo estadístico ni se emplearon informantes. En cambio, la “población” considerada corresponde
al conjunto de configuraciones representadas como subconjuntos de vértices de gráficas, tales
configuraciones son llamadas k-conjuntos, estableciendo su relación con cadenas de códigos,
seleccionando casos particulares para ilustrar las ideas principales.
Las técnicas de producción de datos consistieron en la generación y análisis de objetos matemáticos de
la teoría de gráficas. Se utilizaron representaciones gráficas como recurso de visualización, permitiendo
ilustrar los conceptos de: gráfica, configuración, movimiento de fichas, conexiones entre vértices y
pág. 1088
códigos correctores. Estas representaciones cumplen la función de “instrumentos de apoyo” para
facilitar la comprensión del contenido por parte del lector.
RESULTADOS Y DISCUSIÓN
Un juego sobre gráficas
En el área de la teoría de gráficas, muchas estructuras aparentemente simples pueden dar lugar a ideas
interesantes. Una de ellas surge al observar un juego intuitivo: imagine que se tiene un conjunto de
puntos (llamados vértices, denotado por V) conectados por líneas (llamadas aristas, denotadas por E).
Esta estructura, en matemáticas, se conoce como un grafo o gráfica y se representa como G = (V, E).
Ahora bien, sobre algunos de estos vértices se colocan fichas indistinguibles, siguiendo una regla
sencilla: una ficha puede moverse de un vértice a otro si existe una arista que los conecta, y en todo
momento cada vértice puede contener como máximo una ficha. Para entender mejor esta dinámica,
considere una gráfica camino de n vértices, denotada por Pₙ, que se interpretará como una secuencia
lineal de n vértices conectados consecutivamente, como si se tratara de las casillas de un tablero
dispuesto en línea recta. Por ejemplo, si n = 6, tenemos la gráfica P₆
Suponga que se desea colocar una cantidad fija de k fichas indistinguibles en k de los n vértices del
camino, con k menor o igual que n. Recuerde que la única restricción es que cada vértice puede contener
como máximo una ficha.
Por ejemplo, si se consideran k = 3 fichas en el camino de n = 6 vértices, entonces se podría colocar
dichas fichas inicialmente en los vértices {1, 2, 3}. Luego, podría mover la ficha del vértice 3 al vértice
4, obteniendo la nueva disposición {1, 2, 4}; si después mueve la ficha del vértice 2 al vértice 3, obtendrá
la disposición {1, 3, 4}. Véase la Figura 1, gráficas (a), (b) y (c).
pág. 1089
De esta manera, mediante este tipo de movimientos, se pueden generar múltiples disposiciones distintas
de las 3 fichas sobre el camino. Cada una de estas disposiciones, en las que k vértices distintos están
ocupados por las k fichas, se denomina una configuración. En este ejemplo, configuraciones como {1,
2, 3}, {1, 2, 4} y {1, 3, 4} son algunas de las posibles con k = 3 fichas sobre 3 de los n = 6 vértices. En
total, existen 20 configuraciones distintas, que corresponden a todas las maneras posibles de elegir 3
vértices de los 6 (es decir, el número combinatorio "6 sobre 3", C(6,3)). De manera general, se tienen
en total C(n, k) configuraciones distintas de k fichas en una gráfica G de n vértices.
Una nueva gráfica surge del juego
Una vez obtenidas todas las combinaciones posibles de k fichas colocadas en n vértices del camino (es
decir, C(n, k) configuraciones distintas), se construye una nueva gráfica de la siguiente manera: dos
configuraciones, X y Y, estarán conectadas por una arista en esta nueva gráfica si es posible transformar
una en la otra mediante el movimiento de una sola ficha a lo largo de una arista de la gráfica original Pn.
Específicamente, se requiere que una ficha se desplace desde un vértice ocupado hacia un vértice
adyacente que se encuentre libre de fichas.
Por ejemplo, en el caso del camino P₆ con 6 vértices (gráfica original), las configuraciones X = {1, 2, 4}
y Y = {1, 3, 4} estarán conectadas en la nueva gráfica, ya que se puede obtener una a partir de la otra
desplazando la ficha que se encuentra en el vértice 2 hacia el vértice 3, o viceversa, siendo estos vértices
adyacentes en P₆. De manera general, este proceso puede aplicarse a cualquier gráfica G, dando lugar a
una nueva gráfica denominada gráfica de k-fichas de G, y que se denota como Fₖ(G) (Fabila-Monroy et
al., 2012). En esta nueva gráfica, los vértices representan todas las configuraciones posibles de k fichas
en G, y existe una arista entre dos configuraciones si difieren únicamente en la posición de una sola
pág. 1090
ficha, la cual se ha desplazado a lo largo de una arista de G. En el ejemplo anterior, el procedimiento
genera la gráfica de 3 fichas del camino P₆, denotada como F₃(P₆); véase la figura 2.
Como se mencionó en la introducción, a lo largo de este artículo, se explorará una relación entre las
gráficas de fichas F₃(Pₙ) y el parámetro conocido como empaquetamiento por vértices y ciertos códigos
correctores de errores.
Conjuntos de empaquetamiento por vértices en gráficas
En la sección anterior se introdujeron las gráficas de fichas Fₖ(G), construidas a partir de una gráfica
original o base G considerando las posibles configuraciones de k fichas colocadas en sus vértices. Estas
gráficas tienen implícita la dinámica del movimiento de fichas sobre los vértices de G y permiten
estudiar nuevas propiedades, por ejemplo, la distancia entre los vértices de un subconjunto de vértices
de la nueva gráfica. Una de las preguntas naturales que surgen en este contexto es: ¿Cuántas
configuraciones no se obtienen una de otra a partir de un solo movimiento de una ficha?
Para responder esta pregunta, se empleará un concepto clásico en teoría de gráficas conocido como
conjunto de empaquetamiento por vértices, o simplemente conjunto de empaquetamiento, también
denominado 2-packing en la literatura (Gómez et al., 2018). La idea central consiste en identificar
subconjuntos de vértices cuyos elementos estén mutuamente separados por cierta distancia.
pág. 1091
Formalmente, un subconjunto P de vértices de una gráfica G se denomina conjunto de empaquetamiento
por vértices si, para cualesquiera dos vértices distintos en P, la distancia entre ellos en la gráfica G es
estrictamente mayor que dos. Es decir, el camino más corto que los conecta debe tener al menos tres
aristas. Este tipo de conjuntos tiene aplicaciones relevantes en áreas como la optimización, la
codificación de información y el diseño de redes, donde es fundamental evitar interferencias cercanas
entre nodos o elementos activos.
Respondiendo a la pregunta previa, un problema relacionado con estos conjuntos consiste en determinar
el tamaño máximo que pueden alcanzar dichos vértices. Este valor se conoce como el número de
empaquetamiento de la gráfica G, y se denota como ρ(G). Calcular este número es, en general, una tarea
no trivial, ya que depende de la estructura específica de la gráfica G, es decir, cómo están conectados
los vértices en esta gráfica.
De ahora en adelante, con el objetivo de aclarar los conceptos y/o ideas mediante ejemplos específicos,
se abordará el estudio de conjuntos de empaquetamiento de las gráficas de fichas F₃(Pₙ). Al considerar
estas gráficas, un conjunto de empaquetamiento adquiere una interpretación natural. Se trata de un
subconjunto de configuraciones tales que, cualquier par de ellas están separadas por una distancia
estrictamente mayor que dos, es decir, si X y Y son dos configuraciones en un conjunto de
empaquetamiento, se necesitarán al menos tres movimientos de fichas necesarios para pasar de X a Y.
Por ejemplo, en el caso de la gráfica P₆, un conjunto de empaquetamiento en la gráfica F₃(P₆) está dado
por:
P = {{1,2,3},{1,2,6},{2,3,4},{3,4,5},{4,5,6}},
véase Figura 3. Para ilustrar que P cumple con la condición de empaquetamiento, se observa que pasar
de la configuración {1,2,3} a {1,2,6} requiere tres movimientos consecutivos de la ficha ubicada en el
vértice 3, es decir: 3 → 4 → 5 → 6. De la misma manera, para transformar {1,2,6} en {2,3,4}, se deben
ejecutar los siguientes pasos: primero, mover la ficha del vértice 2 al 3, obteniendo {1,3,6}; luego, mover
la ficha del vértice 6 al 4, pasando por el vértice 5, lo que da {1,3,4}; finalmente, desplazar la ficha del
vértice 1 al vértice 2, resultando en {2,3,4}. Como se puede ver, se realizaron más de dos movimientos
para transformar {1,2,6} en {2,3,4}. Haciendo un análisis exhaustivo, se puede verificar que cada
transición entre pares de configuraciones del conjunto P implica al menos tres movimientos, cumpliendo
pág. 1092
así con la condición requerida. Como el lector puede observar, el número mínimo de pasos para
transformar una configuración en otra no siempre es único y puede variar dependiendo de la estructura
de la gráfica original G.
Códigos correctores
Imagine que se tiene un mensaje secreto, en el que cada palabra está codificada con secuencias de ceros
y unos. Estas secuencias tienen la misma longitud y conforman lo que en teoría de códigos se llama un
código binario. Por ejemplo, las secuencias 1010, 0110 y 0001 son secuencias de un código binario de
longitud 4, ya que contienen 4 dígitos. Dentro de esta colección de códigos, existe una familia especial,
denotado por C, conocida como código binario de peso constante w. En C, el código binario que
determina un mensaje dado tiene exactamente w número de unos, mientras que el resto de sus dígitos
está ocupado por ceros. Así, por ejemplo, la secuencia 10110 tiene peso w = 3 porque contiene
exactamente tres unos.
Ahora bien, ¿qué ocurre si, al transmitir el mensaje, se produce un error? Por ejemplo, tal vez dos bits
adyacentes —un uno y un cero— intercambian sus posiciones. Este tipo de error se denomina
transposición adyacente. Es decir, si transmitimos 10110 pero ocurre una transposición entre el segundo
1 y el 0 ubicado en la segunda posición, obtenemos 11010. En este caso, se requiere que el código sea
pág. 1093
corrector. Un código corrector es aquel que está diseñado de manera que, si ocurre este tipo de error en
un mensaje, es posible identificar de forma única cuál es el mensaje original. Por ejemplo, si un código
contiene solo las secuencias X = 10110 y Y = 01101, y al enviar un mensaje se recibe la secuencia 11010,
se puede deducir que el mensaje original tenía la secuencia X = 10110, porque una sola transposición
adyacente no convierte Y = 01101 en 11010.
En este contexto, un código binario corrector, denotado por B, de peso w=3 es una colección de
secuencias binarias de longitud fija n ≥ 3, donde cada secuencia contiene exactamente tres unos, y que
cumple la siguiente propiedad. Si algunas de las secuencias (o podrían ser todas) de cualquier mensaje
de B tienen a lo más un error, es decir, a lo más una única transposición adyacente, entonces el resultado
no podría haber sido producido por aplicar una transposición adyacente a otra secuencia del mismo
conjunto B. Esta propiedad hace posible corregir ese error y recuperar el mensaje original. De acuerdo
con lo anterior, si el conjunto B={11100, 10101}, entonces B es un código corrector, ya que ninguna
transposición adyacente en ambas secuencias coincide. Esto es, si el mensaje recibido con el error es el
que le ocurrió a la cadena 11100, entonces en ningún momento 10101 pudo ser el mensaje original
enviado. De esta manera, no se tienen ambigüedades sobre la secuencia original enviada. Esto permitiría
corregir el error al recibir un mensaje.
Códigos correctores y gráficas de fichas
En seguida, se verá cómo se relaciona este tipo de códigos correctores con las gráficas de fichas F₃(Pₙ).
Por ejemplo, primero se analizará qué sucede en el caso n = 5 entre los vértices de la gráfica F₃(P₅) y
los códigos correctores de longitud n = 5 y peso w = 3.
Note que una configuración posible es posicionar 3 fichas en el conjunto de vértices {1, 3, 5}, tal
configuración se puede representar como la secuencia binaria 10101, donde los unos indican la posición
de cada ficha. Otra configuración posible, {2, 3, 4}, se representa como 01110. Así, cada configuración
de fichas en Pₙ puede identificarse de manera única con una secuencia binaria de longitud n y peso 3.
Como previamente se vio, en la gráfica F₃(Pₙ), los vértices son todas las configuraciones posibles de
tres fichas en Pₙ, donde dos configuraciones están conectadas por una arista si se puede pasar de una a
la otra moviendo una sola ficha a un vértice vecino vacío. En términos binarios, esta operación
corresponde exactamente a una transposición adyacente entre un 1 y un 0. Por ejemplo, de la
pág. 1094
configuración 10101, se pueden transponer los dígitos en las posiciones 1 y 2, es decir, el 1 y el 0
respectivamente, obteniendo 01101, que representa el movimiento de la ficha de la posición 1 a la 2
partiendo de la configuración {1,3,5}. Este procedimiento nos lleva a la construcción de una gráfica
para modelar este tipo de códigos, denotada por Γₙ³ (Ndjatchi et al. 2024), cuyos vértices son las
secuencias binarias de longitud n y peso 3, donde la adyacencia se define por una única transposición
adyacente, véase Figura 4, b).
Por ejemplo, las secuencias 10110 y 11010 son adyacentes en Γ₅³, así como sus configuraciones
correspondientes {1, 3, 4} y {1, 2, 4} lo son en F₃(P₅), véase Figura 4, a) y b). De acuerdo con este
análisis, se puede ver que las gráficas F₃(Pₙ) y Γₙ³ tienen la misma estructura; en matemáticas, esta
propiedad se resume en que tales gráficas son isomorfas, lo cual se denota matemáticamente como F₃(Pₙ)
≅ Γₙ³, de hecho, de manera general se cumple que Fₖ(Pₙ)
≅
Γₙᵏ para 1<k<n (Ndjatchi et al. 2024).
Una herramienta para construir códigos correctores es emplear las gráficas de fichas y analizar sus
conjuntos de empaquetamiento, que, como ya vimos anteriormente, consisten en un subconjunto de
vértices tales que la distancia (número mínimo de aristas) entre cualquier par de ellos es mayor que dos.
En este caso, eso significa que, si se eligen las secuencias 10011 y 01101 en la gráfica Γₙ³, al menos tres
transposiciones adyacentes son necesarias para pasar de una a la otra, por lo que pueden estar en un
conjunto de empaquetamiento de la gráfica Γₙ³.
Debido al isomorfismo entre F₃(Pₙ) y Γₙ³, un conjunto de empaquetamiento en F₃(Pₙ) equivale a un
conjunto de secuencias binarias de peso 3 en el que la distancia mínima entre cualquier par es mayor
que dos, lo que corresponde exactamente a un código binario de peso 3 capaz de corregir una única
transposición adyacente.
pág. 1095
El problema de determinar el número de empaquetamiento en F₃(Pₙ)
En la sección anterior, se vio que estudiar códigos binarios capaces de corregir errores por transposición
adyacente equivale a estudiar conjuntos de empaquetamiento en las gráficas de fichas F₃(Pₙ). Esta
conexión, que se establece a través del isomorfismo con las gráficas Γₙ³, permite abordar un problema
en teoría de códigos mediante herramientas de la teoría de gráficas. De esta manera, determinar
conjuntos de empaquetamiento en F₃(Pₙ) no sólo es una cuestión combinatoria, sino que tiene
implicaciones directas en la construcción de códigos correctores de mayor tamaño.
Sin embargo, determinar el número de empaquetamiento ρ(Fₖ(Pₙ)) (o equivalentemente ρ(Γₙᵏ)) es un
problema que, desde el punto de vista teórico y computacional, resulta ser altamente complejo. Este
problema es tan difícil como determinar el tamaño máximo de un conjunto independiente de vértices
(es decir, un subconjunto de vértices en el que cada par no son adyacentes entre sí) en una gráfica
arbitraria, un problema conocido por pertenecer a la clase de problemas NP-duros (Garey, 1979).
A pesar de esta dificultad, se han obtenido avances concretos en el caso específico de k = 3, lo cual
corresponde a configuraciones de tres fichas en Pₙ, o secuencias binarias de peso tres. En particular, se
pág. 1096
ha determinado el valor exacto de ρ(F₃(Pₙ)) para valores de n pequeños mediante algoritmos específicos
que exploran de forma exhaustiva el espacio de soluciones posibles (Ndjatchi et al. 2024). Esto es 1 ≤
ρ(F₃(Pₙ)) ≤ 41 para 3 ≤ n ≤ 12. Para valores mayores de n, en el rango 13 ≤ n ≤ 32, se han diseñado
algoritmos constructivos que permiten obtener conjuntos de empaquetamiento lo más grandes posibles.
Estos conjuntos de empaquetamiento proporcionan cotas inferiores para el valor de ρ(F₃(Pₙ)). Por
ejemplo, para los valores de n=13 y n=32 se tienen las siguientes cotas inferiores ρ(F₃(P13)) >49 y
ρ(F₃(P32)) >278 respectivamente. Estos resultados, tanto exactos como aproximados, no sólo enriquecen
la comprensión y estudio de las gráficas de fichas y sus códigos asociados, sino que también aportan
herramientas útiles para entender mejor este tipo de gráficas. A pesar de que el problema general
permanece como un desafío abierto por su complejidad intrínseca, las soluciones obtenidas para valores
específicos de n constituyen un avance parcial dentro del ámbito de los códigos correctores de errores.
CONCLUSIONES
En este trabajo se ha mostrado que el estudio de las gráficas de fichas F₃(Pₙ) proporciona un enfoque
para abordar problemas en teoría de códigos correctores. La conexión se establece a través del
isomorfismo F₃(Pₙ)
≅
Γₙ³, el cuál muestra una relación entre las gráficas de fichas y códigos capaces de
corregir transposiciones adyacentes, permitiendo reinterpretar problemas de diseño de códigos en
términos combinatorios.
Los resultados reportados en la literatura para el número de empaquetamiento de la gráfica de fichas
F₃(Pₙ) muestran un comportamiento no regular en los rangos de n analizados. Para valores pequeños (n
≤ 12), se tienen los valores exactos obtenidos mediante métodos exhaustivos, mientras que para rangos
mayores (13 ≤ n ≤ 32) se han establecido cotas inferiores mediante técnicas constructivas. Mediante el
enfoque metodológico se evidencian las limitaciones impuestas por la NP-dureza del problema, por otro
lado, se destaca la importancia de los enfoques heurísticos para obtener soluciones aproximadas.
El estudio realizado sugiere tres direcciones para investigación futura:
La de terminación de ρ(Fk(Pₙ)) y su relación con códigos correctores de peso constante k > 3.
La determinación exacta de ρ(Fk(Pₙ)) para n> 12.
La búsqueda de patrones combinatorios que permitan predecir comportamientos sin recurrir a cálculos
exhaustivos, y
pág. 1097
El estudio de otras familias de gráficas base, como ciclos Cn y su relación con códigos correctores.
Estas líneas de trabajo podrían conducir a avances tanto en teoría de gráficas como en sus aplicaciones
a sistemas de codificación. La relación entre estas áreas muestra un desarrollo de herramientas teóricas
y aplicadas en el diseño de códigos correctores de errores.
REFERENCIAS BIBLIOGRÁFICAS
1. Alavi, S. H. (2015). A generalisation of Johnson graphs with an application to triple
factorisations. Discrete Mathematics, 338(11), 2026-2036.
2. Alavi, Y., Behzad, M., & Simpson, J. E. (1991). Planarity of double vertex graphs. In Y. Alavi
et al. (Eds.), Graph theory, combinatorics, algorithms, and applications (pp. 472-485). SIAM.
3. Alavi, Y., Behzad, M., Erdős, P., & Lick, D. R. (1991). Double vertex graphs. Journal of
Combinatorics, Information and System Sciences, 16(1), 37-50.
4. Alavi, Y., Lick, D. R., & Liu, J. (2002). Survey of double vertex graphs. Graphs and
Combinatorics, 18(4), 709-715.
5. Alzaga, A., Iglesias, R., & Pignol, R. (2010). Spectra of symmetric powers of graphs and the
Weisfeiler-Lehman refinements. Journal of Combinatorial Theory, Series B, 100(6), 671-682.
6. Audenaert, K., Godsil, C., Royle, G., & Rudolph, T. (2007). Symmetric squares of graphs.
Journal of Combinatorial Theory, Series B, 97(1), 74-90.
7. Castillo, J. H., López Santander, J. J., & Ruiz, H. M. (2025). Introducción a la teoría de códigos
correctores de errores. ISBN: 978-628-7771-20-8.
8. de Alba, H., Carballosa, W., Leaños, J., & Rivera, L. M. (2016). Independence and matching
numbers of some token graphs. arXiv:1606.06370v2.
9. Fabila-Monroy, R., Flores-Peñaloza, D., Huemer, C., Hurtado, F., Urrutia, J., & Wood, D. R.
(2012). Token graphs. Graphs and Combinatorics, 28(3), 365-380. https://doi.org/[falta DOI]
10. Fisher, D. C. (1993). The 2-packing number of complete grid graphs. Ars Combinatoria, 30(1),
261-270.
11. Garey, M. R. (1979). Computers and intractability: A guide to the theory of NP-completeness.
W. H. Freeman.
12. Gómez, J. M., Leaños, J., Ríos-Castro, L. M., & Rivera, L. M. (2018). The packing number of
pág. 1098
the double vertex graph of the path graph. Discrete Applied Mathematics, 247, 327-340.
https://doi.org/[falta DOI]
13. Hill, R. (1986). A first course in coding theory. Oxford University Press.
14. Johnson, S. M. (1962). A new upper bound for error-correcting codes. IRE Transactions on
Information Theory, 8(3), 203-207.
15. Lin, S., & Costello, D. J. (2004). Error control coding: Fundamentals and applications (2nd
ed.). Prentice Hall.
16. MacWilliams, F. J., & Sloane, N. J. A. (1977). The theory of error-correcting codes. North-
Holland.
17. Ndjatchi, C., Escareño Fernández, J. A., Ríos-Castro, L. M., Ibarra-Pérez, T., Correa-Aguado,
H. C., & Pineda Martínez, H. (2024). On the packing number of 3-token graph of the path graph
Pₙ. AIMS Mathematics, 9(5), 11644-11659. https://doi.org/10.3934/math.2024571
18. Rivera, L. M., & Trujillo-Negrete, A. L. (in press). Hamiltonicity of token graphs of fan graphs.
Art Discrete Applied Mathematics.
19. Sayeekumar, N., A. K., S., Karthikeyan, S. P., Sahoo, S. K., & Raglend, I. J. (2015). Graph
theory and its applications in power systems - A review. In 2015 International Conference on
Control, Instrumentation, Communication and Computational Technologies (ICCICCT) (pp.
154-157). IEEE. https://doi.org/10.1109/ICCICCT.2015.7475267
20. Sloane, N. J. A. (2002). On single-deletion-correcting codes. *arXiv:math/0207197*.
https://doi.org/10.48550/arXiv.math/0207197
21. Sloane, N. J. A. (2017). The on-line encyclopedia of integer sequences. https://oeis.org
22. Stauffer, D., & Aharony, A. (2018). Introduction to percolation theory (2nd ed.). CRC Press.
