Grafo umbral

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]

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 ${\displaystyle 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).[3]

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.

• Juego de mayoría ponderada

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