Gráfico de umbral

En teoría de grafos , un grafo umbral es un grafo que se puede construir a partir de un grafo de un vértice mediante la aplicación repetida de las dos operaciones siguientes:

1. Adición de un único vértice aislado al grafo.
2. Adición de un único vértice dominante al grafo, es decir, un único vértice que está 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 comenzando con un gráfico de un solo vértice (vértice 1) y luego agregando vértices negros como vértices aislados y vértices rojos como vértices dominantes, en el orden en que están numerados.

Los gráficos de umbral fueron introducidos por primera vez por Chvátal y Hammer (1977) . Un capítulo sobre gráficos de umbral aparece en Golumbic (1980) , y el libro de Mahadev y Peled (1995) está dedicado a ellos.

Una definición equivalente es la siguiente: un grafo es un grafo umbral si hay un número real y para cada vértice un peso de vértice real tal que para cualesquiera dos vértices , es una arista si y solo si . ${\displaystyle S}$${\displaystyle v}$${\displaystyle w(v)}$${\displaystyle v,u}$${\displaystyle uv}$${\displaystyle w(u)+w(v)>S}$

Otra definición equivalente es esta: un grafo es un grafo umbral si hay un número real y para cada vértice un peso de vértice real tal que para cualquier conjunto de vértices , es independiente si y solo si${\displaystyle T}$${\displaystyle v}$${\displaystyle a(v)}$${\displaystyle X\subsetequ V}$${\displaystyle X}$${\displaystyle \sum _{v\in X}a(v)\leq T.}$

El nombre "grafo umbral" proviene de estas definiciones: S es el "umbral" para la propiedad de ser una arista, o equivalentemente T es el umbral para ser independiente.

Los grafos umbral también tienen una caracterización de grafo prohibido : Un grafo es un grafo umbral si y solo si no hay cuatro de sus vértices que formen un subgrafo inducido que sea un grafo de camino de tres aristas , un grafo de ciclo de cuatro aristas o un emparejamiento de dos aristas .

A partir de la definición que utiliza la adición repetida de vértices, se puede derivar una forma alternativa de describir de manera única un grafo umbral, mediante una cadena de símbolos. es siempre el primer carácter de la cadena y representa el primer vértice del grafo. Cada carácter subsiguiente es o bien , que denota la adición de un vértice aislado (o vértice de unión ), o bien , que denota la adición de un vértice dominante (o vértice de unión ). Por ejemplo, la cadena representa un grafo estrella con tres hojas, mientras que representa un camino con tres vértices. El grafo de la figura se puede representar como${\displaystyle \epsilon }$${\displaystyle u}$${\displaystyle j}$${\displaystyle \epsilon uuj}$${\displaystyle \epsilon uj}$${\displaystyle \epsilon uuujuuj}$

Los grafos umbral son un caso especial de cografos , grafos divididos y grafos trivialmente perfectos . Un grafo es un grafo umbral si y solo si es a la vez un cografo y un grafo dividido. Todo grafo que sea a la vez un grafo trivialmente perfecto y el grafo complementario de un grafo trivialmente perfecto es un grafo umbral. Los grafos umbral también son un caso especial de grafos de intervalo . Todas estas relaciones pueden explicarse en términos de su caracterización por subgrafos inducidos prohibidos. Un cografo es un grafo sin camino inducido en cuatro vértices, P₄ _, y un grafo umbral es un grafo sin P₄, C₄ ni 2K₂ inducidos _. C₄ _es un _ciclo de _cuatro vértices y 2K₂ _es su complemento, es decir, dos aristas disjuntas. Esto también explica por qué los grafos umbral son cerrados al tomar complementos; el P₄ _es autocomplementario, por lo tanto, si un grafo está libre de P₄ _, C₄ _y 2K₂ _, su complemento también lo está.

Heggernes y Kratsch (2007) demostraron que los gráficos de umbral se pueden reconocer en tiempo lineal; si un gráfico no es de umbral, se generará una obstrucción (una de P ₄ , C ₄ o 2K _{2 ).}

• Gráfico de indiferencia
• Grafo serie-paralelo
• Hipergrafos de umbral ^{[ 1 ]}

• Chvátal, Václav ; Hammer, Peter L. (1977), "Agregación de desigualdades en programación entera", en Hammer, PL; Johnson, EL; Korte, BH; et al. (eds.), Estudios en programación entera (Actas del Taller de Bonn, 1975) , Anales de Matemáticas Discretas, vol. 1, Ámsterdam: North-Holland, pp  . 145–162.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Nueva York: Academic Press. 2ª edición, Anales de Matemáticas Discretas, 57 , Elsevier, 2004.
• Heggernes, Pinar ; Kratsch, Dieter (2007), "Algoritmos de reconocimiento de certificación en tiempo lineal y subgrafos inducidos prohibidos" (PDF) , Nordic Journal of Computing , 14 ( 1–2 ): 87–108 (2008), MR  2460558 , archivado del original (PDF) el 24 de abril de 2008..
• Mahadev, NVR; Peled, Uri N. (1995), Gráficos de umbral y temas relacionados , Elsevier.

• Grafos umbral , Sistema de información sobre clases de grafos y sus inclusiones.