Universal vertex
In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. A graph that contains a universal vertex may be called a cone, and its universal vertex may be called the apex of the cone. This terminology should be distinguished from the unrelated usage of these words for universal quantifiers in the logic of graphs, and for apex graphs.
Graphs that contain a universal vertex include the stars, trivially perfect graphs, and friendship graphs. For wheel graphs (the graphs of pyramids), and graphs of higher-dimensional pyramidal polytopes, the vertex at the apex of the pyramid is universal. When a graph contains a universal vertex, it is a cop-win graph, and almost all cop-win graphs contain a universal vertex.
The number of labeled graphs containing a universal vertex can be counted by inclusion–exclusion, showing that there are an odd number of such graphs on any even number of vertices. This, in turn, can be used to show that the property of having a universal vertex is evasive: testing this property may require checking the adjacency of all pairs of vertices. However, a universal vertex can be recognized immediately from its degree: in an -vertex graph, it has degree . Universal vertices can be described by a short logical formula, which has been used in graph algorithms for related properties.
