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. In this context, the universal vertex may also be called the apex of the cone. However, this terminology conflicts with the terminology of apex graphs, in which an apex is a vertex whose removal leaves a planar subgraph.

In special families of graphs

The stars are exactly the trees that have a universal vertex, and may be constructed by adding a universal vertex to an independent set. The wheel graphs, similarly, may be formed by adding a universal vertex to a cycle graph. In geometry, the three-dimensional pyramids have wheel graphs as their skeletons, and more generally the graph of any higher-dimensional pyramid has a universal vertex as the apex of the pyramid.
The trivially perfect graphs always contain a universal vertex, the root of the tree, and more strongly they may be characterized as the graphs in which every connected induced subgraph contains a universal vertex.
The connected threshold graphs form a subclass of the trivially perfect graphs, so they also contain a universal vertex; they may be defined as the graphs that can be formed by repeated addition of either a universal vertex or an isolated vertex.
Every graph with a universal vertex is a dismantlable graph, and almost all dismantlable graphs have a universal vertex.

Other properties

In a graph with vertices, a universal vertex is a vertex whose degree is exactly. Therefore, like the split graphs, graphs with a universal vertex can be recognized purely by their degree sequences, without looking at the structure of the graph.