Gráfico sobrecargado

En teoría de grafos , un grafo sobrelleno es un grafo cuyo tamaño es mayor que el producto de su grado máximo por la mitad de su orden floored , es decir , donde es el tamaño de G , es el grado máximo de G y es el orden de G. El concepto de un subgrafo sobrelleno , un grafo sobrelleno que es un subgrafo , se desprende inmediatamente. Una definición alternativa, más estricta, de un subgrafo sobrelleno S de un grafo G requiere . ${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$ ${\displaystyle |E|}$ ${\displaystyle \displaystyle \Delta (G)}$ ${\displaystyle |V|}$ ${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$

Ejemplos

Todo grafo de ciclo impar de longitud cinco o más está sobrelleno. El producto de su grado (dos) por la mitad de su longitud (redondeada hacia abajo) es uno menos que el número de aristas del ciclo. En términos más generales, todo grafo regular con un número impar de vértices está sobrelleno, porque su número de aristas, (donde es su grado), es mayor que . ${\displaystyle n}$ ${\displaystyle \Delta n/2}$ ${\displaystyle \Delta }$ ${\displaystyle \Delta \lfloor n/2\rfloor }$

Propiedades

Algunas propiedades de los gráficos sobrecargados:

1. Los gráficos sobrecargados son de orden impar.
2. Los gráficos sobrellenos son de clase 2. Es decir, requieren al menos Δ + 1 colores en cualquier coloración de aristas .
3. Un grafo G , con un subgrafo sobrelleno S tal que , es de clase 2. ${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$

Conjetura exagerada

En 1986, Amanda Chetwynd y Anthony Hilton postularon la siguiente conjetura que ahora se conoce como la conjetura del exceso de llenado . ^[1]

Un grafo G es de clase 2 si y sólo si tiene un subgrafo sobrelleno S tal que . ${\displaystyle \Delta (G)>n/3}$ ${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$

Esta conjetura, de ser cierta, tendría numerosas implicaciones en la teoría de grafos, incluida la conjetura de 1-factorización . ^[2]

Algoritmos

Para grafos en los que , hay como máximo tres subgrafos inducidos con sobrellenado, y es posible encontrar un subgrafo con sobrellenado en tiempo polinomial . Cuando , hay como máximo un subgrafo inducido con sobrellenado, y es posible encontrarlo en tiempo lineal . ^[3] ${\displaystyle \Delta \geq n/3}$ ${\displaystyle \Delta \geq n/2}$

Referencias

1. Chetwynd, AG; Hilton, AJW (1986), "Multigrafos estelares con tres vértices de grado máximo" (PDF) , Mathematical Proceedings of the Cambridge Philosophical Society , 100 (2): 303–317, doi :10.1017/S030500410006610X, MR  0848854.
2. Chetwynd, AG; Hilton, AJW (1989), "1-factorización de gráficos regulares de alto grado: un límite mejorado", Discrete Mathematics , 75 (1–3): 103–112, doi : 10.1016/0012-365X(89)90082-4 , MR  1001390.
3. Niessen, Thomas (2001), "Cómo encontrar subgrafos sobrellenos en grafos con un grado máximo grande. II", Electronic Journal of Combinatorics , 8 (1), Documento de investigación 7, MR  1814514.