2025-11-10T02:45:05.969614

On a Conjecture Concerning the Complementary Second Zagreb Index

Saber, Alraqad, Ali et al.
The complementary second Zagreb index of a graph $G$ is defined as $cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$, where $d_u(G)$ denotes the degree of a vertex $u$ in $G$ and $E(G)$ represents the edge set of $G$. Let $G^*$ be a graph having the maximum value of $cM_2$ among all connected graphs of order $n$. Furtula and Oz [MATCH Commun. Math. Comput. Chem. 93 (2025) 247--263] conjectured that $G^*$ is the join $K_k+\overline{K}_{n-k}$ of the complete graph $K_k$ of order $k$ and the complement $\overline{K}_{n-k}$ of the complete graph $K_{n-k}$ such that the inequality $k<\lceil n/2 \rceil$ holds. We prove that (i) the maximum degree of $G^*$ is $n-1$ and (ii) no two vertices of minimum degree in $G^*$ are adjacent; both of these results support the aforementioned conjecture. We also prove that the number of vertices of maximum degree in $G^*$, say $k$, is at most $-\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81}$, which implies that $k<5352n/10000$. Furthermore, we establish results that support the conjecture under consideration for certain bidegreed and tridegreed graphs. In the aforesaid paper, it was also mentioned that determining the $k$ as a function of the $n$ is far from being an easy task; we obtain the values of $k$ for $5\le n\le 149$ in the case of certain bidegreed graphs by using computer software and found that the resulting sequence of the values of $k$ does not exist in "The On-Line Encyclopedia of Integer Sequences" (an online database of integer sequences).
academic

Sobre una Conjetura Relativa al Índice Zagreb Complementario Secundario

Información Básica

  • ID del Artículo: 2501.01295
  • Título: On a Conjecture Concerning the Complementary Second Zagreb Index
  • Autores: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
  • Clasificación: math.CO (Matemática Combinatoria)
  • Fecha de Presentación: 2 de enero de 2025 en arXiv
  • Enlace del Artículo: https://arxiv.org/abs/2501.01295

Resumen

Este artículo investiga problemas de extremalidad del índice Zagreb complementario secundario de grafos. El índice Zagreb complementario secundario se define como cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|, donde du(G)d_u(G) denota el grado del vértice uu en el grafo GG. Los autores realizan un estudio profundo de la conjetura propuesta por Furtula y Oz, que sostiene que el grafo G∗G^* que maximiza cM2cM_2 entre todos los grafos conexos de orden nn es la unión por vértice del grafo completo KkK_k y su complemento K‾n−k\overline{K}_{n-k}, satisfaciendo k<⌈n/2⌉k<\lceil n/2 \rceil.

Antecedentes de Investigación y Motivación

Contexto del Problema

  1. Importancia de los Descriptores Moleculares: Los descriptores moleculares son herramientas fundamentales para el cribado virtual de bibliotecas moleculares y la predicción de propiedades fisicoquímicas moleculares. Los descriptores definidos mediante grafos moleculares en la teoría de grafos químicos se denominan índices topológicos.
  2. Índices Topológicos Basados en Grados: Los índices topológicos definidos sobre la base de grados de vértices tienen amplia aplicación en la teoría de grafos químicos. El índice Zagreb complementario secundario (índice CSZ) es un nuevo índice topológico basado en grados propuesto recientemente.
  3. Problemas de Extremalidad: Determinar la estructura de grafos que optimizan cierto índice topológico bajo restricciones dadas es un problema importante en la teoría de grafos con valor teórico y aplicado.

Motivación de la Investigación

  1. Perfeccionamiento Teórico: Furtula y Oz propusieron en 2025 una conjetura sobre la estructura de grafos extremales del índice CSZ, pero carece de demostración matemática rigurosa.
  2. Complejidad Computacional: Determinar la cantidad de vértices de grado máximo kk en el grafo extremal como función de nn se considera "lejos de ser trivial", requiriendo nuevas herramientas teóricas y métodos computacionales.
  3. Valor Aplicado: Comprender las propiedades extremales del índice CSZ es de importancia significativa para la teoría de grafos químicos y el diseño molecular.

Contribuciones Principales

Las contribuciones principales del artículo incluyen:

  1. Demostración de Propiedades de Grado Máximo del Grafo Extremal: Se prueba que el grado máximo del grafo conexo de orden nn que maximiza cM2cM_2 es n−1n-1.
  2. Revelación de Propiedades de Adyacencia de Vértices de Grado Mínimo: Se demuestra que cualesquiera dos vértices de grado mínimo en G∗G^* no son adyacentes.
  3. Establecimiento de Cota Superior para la Cantidad de Vértices de Grado Máximo: Se prueba que la cantidad kk de vértices de grado máximo en G∗G^* satisface: k≤−23n+32+1652n2−132n+81<5352n10000k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}
  4. Verificación de la Conjetura para Clases de Grafos Especiales: Se demuestra la corrección de la conjetura de Furtula-Oz para grafos de dos grados y tres grados.
  5. Provisión de Datos Computacionales: Mediante software computacional se calculan valores de kk para grafos de dos grados en el rango 5≤n≤1495 \leq n \leq 149, encontrando que la secuencia obtenida no existe en la Enciclopedia en Línea de Secuencias de Números Enteros.

Explicación Detallada de Métodos

Definición de la Tarea

Investigar las propiedades estructurales del grafo que maximiza el índice Zagreb complementario secundario cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G) = \sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2| entre todos los grafos conexos de orden nn.

Teoremas Principales y Métodos de Demostración

Teorema 1 (Proposición 2): Propiedad de Grado Máximo

Enunciado: Si el grafo GG posee el máximo valor de cM2cM_2 entre todos los grafos conexos de orden nn, con n≥4n \geq 4, entonces el grado máximo de GG es n−1n-1.

Esquema de Demostración:

  1. Se supone que el grado máximo Δ<n−1\Delta < n-1, se selecciona un vértice vv de grado Δ\Delta y un vértice uu no adyacente a vv
  2. Se construye el grafo G′G' añadiendo la arista uvuv
  3. Se calcula cM2(G′)−cM2(G)cM_2(G') - cM_2(G), probando que esta diferencia es positiva, lo que contradice la extremalidad de GG

Teorema 2 (Proposición 3): No Adyacencia de Vértices de Grado Mínimo

Enunciado: En el grafo extremal GG, cualesquiera dos vértices de grado mínimo no son adyacentes.

Método de Demostración: Mediante reducción al absurdo, se supone la existencia de vértices de grado mínimo adyacentes y se demuestra que la eliminación de la arista entre ellos aumentaría cM2cM_2.

Teorema 3 (Proposición 4): Cota Superior para la Cantidad de Vértices de Grado Máximo

Técnica de Demostración:

  1. Se selecciona una arista conectando un vértice de grado máximo y uno de grado mínimo para su eliminación
  2. Se analiza el impacto de la eliminación de esta arista sobre el valor de cM2cM_2
  3. Se establece una desigualdad cuadrática respecto a kk
  4. Se resuelve para obtener la fórmula de cota superior

Análisis de Clases de Grafos Especiales

Caracterización Completa de Grafos de Dos Grados (Proposición 5)

Para grafos conexos de dos grados de orden nn con grado máximo n−1n-1, se demuestra que: cM2(G)≤k(n−k)((n−1)2−k2)cM_2(G) \leq k(n-k)((n-1)^2 - k^2) La igualdad se cumple si y solo si G=Kk+K‾n−kG = K_k + \overline{K}_{n-k}.

Análisis de Grafos de Tres Grados (Proposición 7)

Utilizando las herramientas de desigualdad establecidas en el Lema 6, se realiza una clasificación por casos de grafos de tres grados, demostrando que en cada caso existe una estructura Kt+K‾n−tK_t + \overline{K}_{n-t} más óptima.

Configuración Experimental

Método Computacional

Se utiliza software computacional para realizar cálculos exhaustivos de grafos de dos grados en el rango 5≤n≤1495 \leq n \leq 149, determinando el valor óptimo de kk correspondiente a cada nn.

Validación de Datos

La secuencia de valores de kk obtenida se compara con la base de datos "The On-Line Encyclopedia of Integer Sequences".

Resultados Experimentales

Resultados Computacionales Principales

La Tabla 1 presenta los valores óptimos de kk correspondientes a nn de 5 a 149, por ejemplo:

  • Para n=5n=5, k=2k=2
  • Para n=10n=10, k=4k=4
  • Para n=20n=20, k=8k=8
  • Para n=50n=50, k=19k=19
  • Para n=100n=100, k=39k=39
  • Para n=149n=149, k=58k=58

Novedad de la Secuencia

La secuencia obtenida 2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,...2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,... no existe en la base de datos OEIS, indicando que se trata de una nueva secuencia de números enteros.

Verificación Teórica

El Corolario 2 confirma que para n≥11n \geq 11, el valor óptimo de kk satisface 3n10<k<4n10\frac{3n}{10} < k < \frac{4n}{10}, lo cual es consistente con los resultados computacionales.

Trabajos Relacionados

Evolución del Índice Zagreb

  1. Índices Zagreb Clásicos: El índice Zagreb secundario M2(G)=∑uv∈E(G)dudvM_2(G) = \sum_{uv \in E(G)} d_u d_v es un índice clásico en la teoría de grafos químicos
  2. Métodos Geométricos: El método geométrico introducido por Gutman proporciona una nueva perspectiva para la investigación de índices topológicos basados en grados
  3. Índices Complementarios: El índice CSZ ha sido propuesto independientemente en múltiples investigaciones bajo diferentes nombres (índice nano Zagreb, índice F-menos, etc.)

Teoría de Grafos Extremales

La investigación en este artículo continúa las técnicas clásicas de la teoría de grafos extremales, particularmente el método de análisis de cambios en índices topológicos mediante transformaciones de grafos.

Conclusiones y Discusión

Conclusiones Principales

  1. Confirmación de Propiedades Estructurales: Se demuestran dos propiedades estructurales clave mencionadas en la conjetura de Furtula-Oz
  2. Establecimiento de Restricciones Cuantitativas: Se proporciona una cota matemática rigurosa para la cantidad de vértices de grado máximo
  3. Resolución Completa de Casos Especiales: Se verifica completamente la corrección de la conjetura para grafos de dos grados y tres grados

Limitaciones

  1. Demostración Completa del Caso General: Para grafos conexos generales, la conjetura aún no ha sido completamente demostrada
  2. Ausencia de Fórmula Exacta: La forma exacta de kk como función de nn sigue siendo desconocida
  3. Restricción del Rango Computacional: Actualmente solo se han calculado casos hasta n=149n=149

Direcciones Futuras

  1. Demostración Completa: Buscar una demostración matemática completa de la conjetura de Furtula-Oz
  2. Comportamiento Asintótico: Investigar las propiedades asintóticas y el comportamiento límite de k/nk/n
  3. Optimización de Algoritmos: Desarrollar algoritmos más eficientes para calcular casos con valores mayores de nn
  4. Investigación Generalizada: Extender los métodos a la investigación de otros tipos de índices topológicos

Evaluación Profunda

Fortalezas

  1. Contribuciones Teóricas Sólidas: Proporciona múltiples demostraciones matemáticas rigurosas que avanzan significativamente la comprensión de las propiedades extremales del índice CSZ
  2. Fuerte Innovación Metodológica: Combina técnicas de transformación de grafos y análisis de desigualdades, con métodos de demostración de carácter general
  3. Trabajo Computacional Detallado: La verificación computacional a gran escala proporciona un apoyo sólido para el análisis teórico
  4. Escritura Clara y Normativa: Los enunciados de teoremas son precisos, la lógica de las demostraciones es clara y se ajusta a las normas de escritura matemática

Deficiencias

  1. Resolución Incompleta de la Conjetura Central: Aunque proporciona resultados de apoyo significativos, la demostración completa de la conjetura de Furtula-Oz sigue siendo deficiente
  2. Profundidad Técnica Limitada: Principalmente utiliza técnicas de teoría de grafos relativamente elementales, posiblemente requiriendo herramientas matemáticas más profundas
  3. Contexto de Aplicación Insuficiente: La discusión sobre el significado específico del índice CSZ en aplicaciones químicas es limitada

Impacto

  1. Valor Teórico: Proporciona nuevos resultados teóricos para la teoría de grafos extremales y la teoría de grafos químicos
  2. Valor Metodológico: Las técnicas de demostración pueden generalizarse a la investigación de otros índices topológicos
  3. Valor Computacional: Los datos y secuencias proporcionados tienen valor de referencia para investigaciones posteriores

Escenarios de Aplicabilidad

Los métodos y resultados de este artículo son aplicables a:

  1. Investigación de descriptores moleculares en teoría de grafos químicos
  2. Análisis teórico de teoría de grafos extremales
  3. Problemas de optimización de índices topológicos basados en grados
  4. Optimización combinatoria de estructuras de grafos

Referencias Bibliográficas

El artículo cita 15 referencias relacionadas, abarcando múltiples aspectos incluyendo descriptores moleculares, fundamentos de teoría de grafos, teoría del índice Zagreb, etc. El artículo de 2025 de Furtula y Oz constituye la base directa de esta investigación.