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.