Threshold graph
Graph formed by adding isolated or universal vertices / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Threshold graph?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
- Addition of a single isolated vertex to the graph.
- Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/00/Threshold_graph.png/260px-Threshold_graph.png)
For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.
Threshold graphs were first introduced by Chvátal & Hammer (1977). A chapter on threshold graphs appears in Golumbic (1980), and the book Mahadev & Peled (1995) is devoted to them.