Gráfico de umbral

En la teoría de grafos, un gráfico de umbral es un gráfico que se puede construir a partir de un gráfico de un solo vértice realizando secuencialmente las siguientes dos operaciones:

  1. Agregar un vértice aislado al gráfico
  2. Agregar un vértice dominante al gráfico, es decir, un solo vértice conectado a todos los demás vértices.

Por ejemplo, el gráfico de la figura es un gráfico de umbral. Se puede construir a partir de un vértice (vértice 1) y añadiendo vértices negros como vértices aislados y vértices rojos como vértices dominantes en orden numérico.

Los gráficos de umbral fueron introducidos por Chvatal y Hammer [1] . El capítulo sobre gráficos apareció en el libro de Golumbik [2] , mientras que el libro de Mahadev y Peled [3] está enteramente dedicado a los gráficos de umbral.

Definiciones alternativas

Una definición equivalente es la siguiente: un gráfico es un umbral si existe un número real y para cada vértice se le da un peso tal que para dos vértices cualesquiera , es una arista si y solo si .

Otra definición equivalente: un grafo es umbral si existe un número real y para cada vértice se le da un peso tal que para cualquier conjunto de vértices , es independiente si y sólo si

El nombre "gráfico de umbral" proviene de la definición: S es un "umbral" para que la propiedad tenga un borde, o de manera equivalente, T es un umbral para que un conjunto sea independiente.

Descomposición

A partir de la definición que utiliza la adición secuencial de vértices, se puede obtener una forma alternativa de describir de forma única el gráfico de umbral en el sentido de una cadena de caracteres. siempre sirve como el primer carácter de la cadena y representa el primer vértice del gráfico. Cada carácter subsiguiente será , lo que significa un vértice aislado, o , lo que significa agregar un vértice dominante. Por ejemplo, una cadena representa una estrella con tres hojas, pero representa un camino de tres vértices. La gráfica de la figura se puede representar con la línea

Clases conectadas de grafos y reconocimiento

Los gráficos de umbral son un caso especial de los cografos , los gráficos divididos y los gráficos trivialmente perfectos [4] . Cualquier gráfico que sea tanto un cografo como un gráfico dividido es un gráfico de umbral. Cualquier gráfico que sea a la vez un gráfico trivialmente perfecto y el complemento de un gráfico trivialmente perfecto es un gráfico de umbral. Los gráficos de umbral también son un caso especial de los gráficos de intervalo . Todas estas conexiones pueden explicarse en términos de su caracterización por subgrafos generados prohibidos. Un cografo es un grafo sin caminos generados con cuatro vértices, P 4 , y los grafos de umbral son grafos de bases de subgrafos generados P 4 , C 4 o 2K 2 [5] . C 4 es un ciclo de cuatro vértices, y 2K 2 es su complemento, es decir, dos aristas separadas. Esto también explica por qué los gráficos de umbral son de complemento cerrado. P 4 es autocomplementario, y por tanto, si el grafo no contiene los subgrafos generados P 4 , C 4 y 2K 2 , su complemento tampoco los tendrá [6] .

Heggernes y otros han demostrado que los gráficos de umbral se pueden reconocer en tiempo lineal. Si el gráfico no es un umbral, se indicará un obstáculo en forma de P 4 , C 4 o 2K 2 .

Véase también

Notas

  1. ↑ Chvatal, Martillo, 1977 .
  2. ↑ Golumbic, 1980 .
  3. ↑ Mahadev, Peled, 1995 .
  4. ↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , p. 227, Corolario 50.11.
  5. ↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , p. 224, Corolario 50.3.
  6. ↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , p. 227, Corolario 50.12.

Literatura

Enlaces