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. (It is not to be confused with a universally quantified vertex in the logic of graphs.)

A graph with a universal vertex, u

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.^[1] 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.^[2] In geometry, the three-dimensional pyramids have wheel graphs as their skeletons,^[3] 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.^[4] 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).^[5]

The friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966) 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.^[6]

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. Any removal sequence that leaves the universal vertex in place, removing all of the other vertices, fits this definition. Almost all dismantlable graphs have a universal vertex, in the sense that the fraction of ${\displaystyle n}$ -vertex dismantlable graphs that have a universal vertex tends to one in the limit as ${\displaystyle n}$  goes to infinity.^[7]

As a special case of the observation that the domination number increases at most multiplicatively in strong products of graphs,^[8] a strong product has a universal vertex if and only if both of its factors do.

Recognition

In a graph with n vertices, a universal vertex is a vertex whose degree is exactly n − 1. 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.

The property of having a universal vertex can be expressed by a formula in the first-order logic of graphs. Using ${\displaystyle \sim }$  to indicate the adjacency relation in a graph, a graph ${\displaystyle G}$  has a universal vertex if and only if it models the formula

$${\displaystyle \exists u\forall v{\bigl (}(u\neq v)\Rightarrow (u\sim v){\bigr )}.}$$

 

The existence of this formula, and its small number of alternations between universal and existential quantifers, can be used in a fixed-parameter tractable algorithm for testing whether all components of a graph can be made to have universal vertices by ${\displaystyle k}$  steps of removing a vertex from each component.^[9]

References

1. Larrión, F.; de Mello, C. P.; Morgana, A.; Neumann-Lara, V.; Pizaña, M. A. (2004), "The clique operator on cographs and serial graphs", Discrete Mathematics, 282 (1–3): 183–191, doi:10.1016/j.disc.2003.10.023, MR 2059518.
2. Bonato, Anthony (2008), A course on the web graph, Graduate Studies in Mathematics, vol. 89, Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, p. 7, doi:10.1090/gsm/089, ISBN 978-0-8218-4467-0, MR 2389013.
3. Pisanski, Tomaž; Servatius, Brigitte (2013), Configuration from a Graphical Viewpoint, Springer, p. 21, doi:10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4
4. Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society, 13 (5): 789–795, doi:10.2307/2034179, JSTOR 2034179, MR 0172273.
5. Chvátal, Václav; Hammer, Peter Ladislaw (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.
6. Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235.
7. Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), "Almost all cop-win graphs contain a universal vertex", Discrete Mathematics, 312 (10): 1652–1657, doi:10.1016/j.disc.2012.02.018, MR 2901161.
8. Lakshmanan, S. Aparna; Vijayakumar, A. (2009), "A note on some domination parameters in graph products", Journal of Combinatorial Mathematics and Combinatorial Computing, 69: 31–37, MR 2517304
9. Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M. (2021), "Parameterized complexity of elimination distance to first-order logic properties", 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, IEEE, pp. 1–13, arXiv:2104.02998, doi:10.1109/LICS52264.2021.9470540, S2CID 233169117

External links

• Weisstein, Eric W., "Cone Graph", MathWorld