Conjetura de desequilibrio

Problema sin resolver en matemáticas

Conjetura: Si para todas las aristas${\displaystyle e\in E(G)}$tenemos${\displaystyle {\text{imb}}(e)>0}$, entonces${\displaystyle M_{G}}$es gráfico.

Más problemas sin resolver en matemáticas

La conjetura del desequilibrio es un problema abierto en la teoría de grafos que trata sobre si las secuencias de desequilibrio de aristas son gráficas, planteada formalmente por primera vez por Kozerenko y Skochko en 2014. ^{[ 1 ]}

Para un grafo simple no dirigido${\displaystyle G}$, el desequilibrio de un borde${\displaystyle e=uv}$se define como:

${\displaystyle {\text{imb}}(e)=|\deg(u)-\deg(v)|}$

dónde${\displaystyle \deg(u)}$y${\displaystyle \deg(v)}$denotan los grados de los vértices${\displaystyle u}$y${\displaystyle v}$respectivamente.

La secuencia de desequilibrio${\displaystyle M_{G}}$es el multiconjunto de todos los desequilibrios de aristas en${\displaystyle G}$.

Una secuencia de enteros no negativos se denomina gráfica si es la secuencia de grados de algún grafo. Cabe señalar que el término a veces admite un multigrafo , pero aquí se define como la secuencia de grados de un grafo simple .

Un gráfico${\displaystyle G}$Se denomina gráfico de desequilibrio si su secuencia de desequilibrio${\displaystyle M_{G}}$es gráfico. ^{[ 2 ]}

Conjetura de desequilibrio: Si para todas las aristas${\displaystyle e\in E(G)}$tenemos${\displaystyle {\text{imb}}(e)>0}$, entonces${\displaystyle M_{G}}$es gráfico.

En otras palabras, si ninguna arista de un grafo conecta vértices de igual grado, entonces el multiconjunto de desequilibrios de aristas forma una secuencia de grados válida para algún grafo simple.

El concepto de desequilibrio de aristas fue introducido por Albertson en 1997 como una medida de irregularidad de grafos. ^{[ 3 ]} La irregularidad de un grafo${\displaystyle G}$se define como:

${\displaystyle I(G)=\sum _{uv\in E(G)}|\deg(u)-\deg(v)|}$

A veces se le llama índice de Albertson y se denota como${\displaystyle \operatorname {Alb} (G)}$en la literatura. Si bien una cantidad considerable de investigaciones se ha centrado en los límites de la irregularidad de los grafos, Kozerenko y Skochko fueron los primeros en estudiar sistemáticamente las secuencias desequilibradas como objetos de interés por derecho propio.

La conjetura del desequilibrio se ha verificado computacionalmente para todos los grafos con como máximo 9 vértices que satisfacen la condición de que todas las aristas tengan un desequilibrio positivo. ^{[ 1 ]} Esto se mejoró posteriormente para grafos con como máximo 12 vértices. ^{[ 2 ]}

Se ha demostrado que varias clases de grafos tienen secuencias de desequilibrio gráfico. Kozerenko y Skochko demostraron que las siguientes clases presentaban desequilibrio gráfico: ^{[ 1 ]}

• Todos los árboles
• Grafos en los que todos los vértices que no son hojas forman una camarilla (grafos cl)
• Extensiones completas de caminos
• Extensiones completas de ciclos
• Extensiones completas de grafos completos
• Grafos con desequilibrio constante de aristas

Kozerenko y Serdiuk establecieron clases adicionales de gráficos de desequilibrio: ^{[ 2 ]}

• Todos los grafos unicíclicos (grafos con exactamente un ciclo)
• Grafos antirregulares (grafos con exactamente un par de vértices que tienen el mismo grado)
• Tres clases especiales de grafos de bloques :
  • Gráficos de bloques que tienen todos los vértices de corte en un solo bloque.
  • Grafos de bloques en los que los vértices cortados inducen una estrella
  • Grafos de bloques en los que los vértices de corte inducen un camino.

También se sabe que los grafos irregulares por pasos (grafos en los que el desequilibrio de cada arista es 1) tienen secuencias de desequilibrio gráfico; todas ellas tienen la forma de un número determinado de caminos disjuntos de 2 lados.

Se ha demostrado que varias operaciones gráficas conservan la propiedad de ser gráficas desequilibradas: ^{[ 2 ]}

• Si${\displaystyle G_{1}}$y${\displaystyle G_{2}}$Si son gráficos desequilibrados, entonces su unión disjunta también es un gráfico desequilibrado.
• La unión de grafos con grafos vacíos suficientemente grandes es un grafo desequilibrado.
• Si${\displaystyle G}$es un gráfico de desequilibrio, entonces también lo es${\displaystyle G+K_{1}}$(la unión con un solo vértice)
• El gráfico doble de un gráfico de desequilibrio también es un gráfico de desequilibrio

El problema sería trivial si${\displaystyle M_{G}}$Se permitió que fuera la secuencia de grados para un pseudografo , porque el índice de Albertson siempre es un número par, y cualquier secuencia no creciente de enteros positivos con una suma par es la secuencia de grados de un pseudografo.

Una conjetura relacionada se refiere al desequilibrio medio de un grafo no vacío.${\displaystyle G}$, definido como:

${\displaystyle m(G)={\frac {I(G)}{|E(G)|}}}$

Conjetura del desequilibrio medio: Si${\displaystyle m(G)\geq 2}$, entonces${\displaystyle M_{G}}$es gráfico. ^{[ 1 ]}

Esta conjetura fue refutada por Kozerenko y Serdiuk en 2023, quienes demostraron que para cada número real${\displaystyle c>0}$Existe un desequilibrio en el gráfico no gráfico.${\displaystyle G}$con${\displaystyle I(G)\geq c\cdot |E(G)|}$. ^{[ 2 ]}

Conjetura del grafo bicíclico: Existe exactamente un grafo bicíclico no gráfico desequilibrado y conexo (demostrado que existe entre grafos con como máximo 21 vértices). ^{[ 2 ]}

Conjetura del grafo de bloques: Todos los grafos de bloques son grafos desequilibrados. ^{[ 2 ]}

Esta conjetura se ha verificado para todos los grafos de bloques con un máximo de 13 vértices. Una versión más débil conjetura que todos los grafos de líneas de árboles (que son exactamente grafos de bloques sin garras) son grafos de desequilibrio.

• secuencia de grados
• Teorema de Erdős-Gallai