Gráfico de umbral

Gráfico formado por la suma de vértices aislados o universales

Un ejemplo de un 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 aplicaciones repetidas de las siguientes dos operaciones:

1. Adición de un solo vértice aislado al gráfico.
2. Adición de un único vértice dominante al gráfico, 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 primeros gráficos de umbral fueron introducidos por Chvátal y Hammer (1977). En Golumbic (1980) aparece un capítulo sobre ellos, y el libro Mahadev y Peled (1995) está dedicado a ellos.

Definiciones alternativas

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 gráfico es un gráfico de 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\subseteq V}$ ${\displaystyle X}$ ${\displaystyle \sum _{v\in X}a(v)\leq T.}$

El nombre "gráfico de umbral" proviene de estas definiciones: S es el "umbral" para la propiedad de ser un borde, o equivalentemente T es el umbral para ser independiente.

Los gráficos de umbral también tienen una caracterización de gráfico prohibido : un gráfico es un gráfico de umbral si y solo si ninguno de sus cuatro vértices forma un subgráfico inducido que es un gráfico de ruta de tres aristas , un gráfico de ciclo de cuatro aristas o un gráfico coincidente de dos aristas .

Descomposición

A partir de la definición que utiliza la adición repetida de vértices, se puede derivar una forma alternativa de describir de forma única un grafo de 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 posterior es , que denota la adición de un vértice aislado (o vértice de unión ), o , que denota la adición de un vértice dominante (o vértice de unión ). Por ejemplo, la cadena representa un grafo de estrella con tres hojas, mientras que representa un camino en 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}$

Clases relacionadas de gráficos y reconocimiento

Los grafos de umbral son un caso especial de cografos , grafos divididos y grafos trivialmente perfectos . Un grafo es un grafo de umbral si y solo si es tanto un cografo como un grafo dividido. Todo grafo que sea tanto un grafo trivialmente perfecto como el grafo complementario de un grafo trivialmente perfecto es un grafo de umbral. Los grafos de umbral también son un caso especial de grafos de intervalo . Todas estas relaciones se pueden explicar 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 de umbral es un grafo sin P ₄ inducido , C ₄ ni 2K ₂ . 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 de umbral son complementos cerrados; el P ₄ es autocomplementario, por lo tanto, si un grafo es libre de P ₄ -, C ₄ - y 2K ₂ , su complemento también lo es.

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 ).}

Véase también

• Gráfica de indiferencia
• Gráfica serie-paralela
• Hipergrafos de umbral ^[1]

Referencias

1. Reiterman, enero; Rödl, Vojtěch; Šiňajová, Edita; Tůma, Miroslav (1 de abril de 1985). "Hipergrafías de umbral". Matemáticas Discretas . 54 (2): 193–200. doi : 10.1016/0012-365X(85)90080-9 . ISSN  0012-365X.

• 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 (Proc. Worksh. Bonn 1975) , Anales de matemáticas discretas, vol. 1, Ámsterdam: Holanda Septentrional, págs. 145–162.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Nueva York: Academic Press. 2da edición, Annals of Discrete Mathematics, 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.
• Mahadev, NVR; Peled, Uri N. (1995), Gráficos de umbral y temas relacionados , Elsevier.

Enlaces externos

• Gráficos de umbral, Sistema de Información sobre Clases de Grafos y sus Inclusiones.