Grafo umbral

Un ejemplo de 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.

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.^[1] 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.^[2]

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 sólo si .

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 caracter de la cadena, y representa el primer vértice del grafo. Cada caracter 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 con pesos (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).^[3]

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 con pesos

Notas

Bibliografía

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