Concept
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. (It is not to be confused with a universally quantified vertex in the logic of graphs.) 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. 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 (the comparability graphs of order-theoretic trees) 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 (one with no incident edges). The friendship theorem of states that, if every two vertices in a finite graph have exactly one shared neighbor, then the graph contains a universal vertex. The graphs described by this theorem are the friendship graphs, formed by systems of triangles connected together at a common shared vertex, the universal vertex. Every graph with a universal vertex is a dismantlable graph, meaning that it can be reduced to a single vertex by repeatedly removing vertices whose closed neighborhoods are subsets of other vertices' closed neighborhoods.
