Determinación del número b-cromático de coronas de vecindad de vértices de subdivisión

Información Básica

• ID del artículo: 2302.13667
• Título: Determinación del número b-cromático de coronas de vecindad de vértices de subdivisión
• Autores: Raúl M. Falcón (Universidad de Sevilla, España), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
• Clasificación: math.CO (Combinatoria)
• Fecha de publicación: 27 de febrero de 2023
• Enlace del artículo: https://arxiv.org/abs/2302.13667

Resumen

Sean $G$ y $H$ dos grafos, cada uno siendo un camino, un ciclo o un grafo estrella. Este artículo determina el número b-cromático de cada grafo corona de vecindad de vértices de subdivisión $G\boxdot H$ o $G\boxdot K_n$, donde $K_n$ es el grafo completo de orden $n$. Para grafos $K_n\boxdot G$ con grado $m$ no mayor que $n+2$, también se establecen resultados correspondientes. Todas las pruebas se acompañan con ejemplos ilustrativos.

Antecedentes de investigación y motivación

Contexto del problema

1. Concepto del número b-cromático: Irving y Manlove introdujeron en 1999 el concepto de coloración b-cromática de grafos, que es una coloración $k$-propia especial que requiere que cada color tenga un vértice b (un vértice adyacente a vértices de todos los demás colores).
2. Complejidad computacional: Determinar el número b-cromático de un grafo es NP-difícil en general, pero es resoluble en tiempo polinomial para árboles.
3. Investigación de productos de grafos: Existe una amplia investigación sobre el número b-cromático de varios productos de grafos, como el producto cartesiano, producto directo, producto fuerte, producto lexicográfico, etc.

Motivación de la investigación

1. Perfeccionamiento teórico: El grafo corona de vecindad de vértices de subdivisión (SVN corona) es un método importante de construcción de grafos, pero su investigación del número b-cromático es relativamente escasa.
2. Sistematización de métodos: Es necesario estudiar sistemáticamente el número b-cromático de coronas SVN de clases de grafos fundamentales (caminos, ciclos, grafos estrella, grafos completos).
3. Valor aplicado: El número b-cromático tiene importantes aplicaciones en problemas prácticos como coloración de redes y asignación de frecuencias.

Contribuciones principales

1. Determinación completa del número b-cromático de coronas SVN de clases de grafos fundamentales: Para caminos $P_n$, ciclos $C_n$, grafos estrella $S_n$ y sus coronas SVN con caminos, ciclos, grafos estrella y grafos completos, se proporcionan fórmulas exactas del número b-cromático.
2. Establecimiento de resultados parciales para coronas SVN de grafos completos: Para $K_n\boxdot G$ con grado $m$ no superior a $n+2$, se determina su número b-cromático.
3. Provisión de métodos de prueba constructivos: Todos los resultados se demuestran mediante la construcción de coloraciones b-cromáticas óptimas específicas, acompañadas de ejemplos gráficos detallados.
4. Desarrollo de un marco de análisis sistemático: Se establece un método general y herramientas técnicas para analizar el número b-cromático de coronas SVN.

Explicación detallada de métodos

Definición de la tarea

Entrada: Dos grafos $G$ y $H$, donde $G,H \in \{P_n, C_n, S_n, K_n\}$Salida: El número b-cromático $\varphi(G\boxdot H)$ del grafo corona SVN Restricciones: Para el caso $K_n\boxdot G$, se requiere que $m(K_n\boxdot G) \leq n+2$

Construcción de coronas SVN

Dado un grafo $G$ y un grafo $H$, el proceso de construcción del grafo corona SVN $G\boxdot H$:

1. Comenzar con el grafo de subdivisión $S(G)$ de $G$ (insertar un nuevo vértice en cada arista)
2. Añadir $|V(G)|$ copias vértice-disjuntas de $H$
3. Conectar todos los vértices en la vecindad de cada vértice original $u_i$ en $S(G)$ a todos los vértices de la $(i+1)$-ésima copia de $H$

Herramientas técnicas clave

1. Concepto de grado m

Para un grafo $G$ de orden $n$, su grado $m$ se define como: $m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}|$ donde los vértices se ordenan por grado no creciente.

2. Límites fundamentales

• Límite inferior: $\chi(G) \leq \varphi(G)$ (el número cromático no excede el número b-cromático)
• Límite superior: $\varphi(G) \leq \Delta(G) + 1$ (el número b-cromático no excede el grado máximo más uno)
• Límite de grado m: $\varphi(G) \leq m(G)$

3. Fórmulas de grado para coronas SVN

Para un vértice $v$ en $G\boxdot H$: