Universal vertex
- Not to be confused with a universally quantified vertex in the logic of graphs.
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. In a graph with n vertices, it 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.
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.
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, 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.[3] 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).[4]
Every graph with a universal vertex is a dismantlable graph, and almost all dismantlable graphs have a universal vertex.[5]
References
- ↑ 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.
- ↑ Bonato, Anthony (2008), A course on the web graph, Graduate Studies in Mathematics, 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.
- ↑ Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society, 13: 789–795, MR 0172273.
- ↑ 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., Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, 1, Amsterdam: North-Holland, pp. 145–162.
- ↑ 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.