Grafo umbral

En teoría de grafos, un grafo umbral (mejor conocido en inglés como threshold graph) es un grafo que puede ser construido desde un único vértice aplicando repetidamente cualquiera de las siguientes dos operaciones:

1. Adición de un vértice aislado al grafo, es decir, de un vértice con grado 0.
2. Adición de un vértice dominante al grafo, es decir, de un vértice que está conectado a todos los demás vértices.

Un ejemplo de grafo umbral.

Por ejemplo, el grafo de la figura es un grafo umbral. Puede construirse comenzando con el vértice 1, y luego añadiendo vértices negros como vértices aislados y vértices rojos como vértices dominantes, siguiendo el orden en que están enumerados.

Historia

Estos grafos fueron por primera vez introducidos por Václav Chvátal y Peter Hammer en su artículo de 1977.​ Un capítulo completo sobre grafos umbrales aparece en el libro de Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs. La referencia más completa en el tema es el libro de Mahadev y Peled, Threshold Graphs and Related Topics.​

Definiciones alternativas

Una definición equivalente puede darse utilizando una función umbral: un grafo es un threshold graph si existe un número real S y para cada vétice v existe un peso w(v) para dicho vértice, tal que para cualesquiera dos vértices v, u, (u,v) es una arista si y solo si $w(u)+w(v)\geq S$.

A partir de la primera definición, se puede derivar una manera alternativa de describir estos grafos mediante strings o cadenas de caracteres. ε es siempre el primer carácter de la cadena, y representa el primer vértice del grafo. Cada carácter subsecuente es o bien una a, que denota la adición de un vértice aislado, o bien una d, que denota la adición de un vértice dominante. Así por ejemplo, la cadena εuuj representa un grafo estrella con tres hojas, mientras que εuj es un camino de tres vértices. El grafo de la primera figura puede representarse como εuuujuuj.

En teoría de juegos cooperativos, un grafo umbral puede representarse como un juego de mayoría ponderada (o weighted game), donde cada vértice del grafo representa un jugador, y si una arista conecta dos vértices i, j, entonces tanto el conjunto {i, j} como cada uno de sus superconjuntos es una coalición ganadora. Por esta razón, a estos grafos también se les suele llamar grafos con pesos (en inglés, weighted graphs).​

Propiedades

Los threshold graphs son un caso especial de cografos, grafo dividido (split graphs), grafos trivialmente perfectos y grafos intervalos. Cada grafo que es al mismo tiempo un cografo y un split graph, es un threshold graph. Cada grafo que es al mismo tiempo trivialmente perfecto y el grafo complemento de un grafo trivialmente perfecto es un threshold graph.

Véase también

• Juego de mayoría ponderada

Bibliografía

• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press .. 2.ª edición, Annals of Discrete Mathematics, 57, Elsevier, 2004.

• Datos: Q943345