Universal vertex
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/92/Universal_vertex.svg/220px-Universal_vertex.svg.png)
In
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
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] 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]
In geometry, the three-dimensional pyramids have wheel graphs as their skeletons,[5] and more generally a higher-dimensional pyramid is a polytope whose faces of all dimensions connect an apex vertex to all the faces of a lower-dimensional base, including all of the vertices of the base. The polytope is said to be pyramidal at its apex, and it may have more than one apex. However, the existence of neighborly polytopes means that the graph of a polytope may have a universal vertex, or all vertices universal, without the polytope itself being a pyramid.[6]
The
Every graph with a universal vertex is a
When a graph has a universal vertex, the vertex set consisting only of that vertex is a dominating set, a set that includes or is adjacent to every vertex. For this reason, in the context of dominating set problems, a universal vertex may also be called a dominating vertex.[10] For the strong product of graphs , the domination numbers and obey the inequalities This implies that a strong product has a dominating vertex if and only if both of its factors do; in this case the upper bound on its dominating number is one, and in any other case the lower bound is greater than one.[11]
Combinatorial enumeration
The number of
In each term of the sum, is the number of vertices chosen to be universal, and is the number of ways to make this choice. is the number of pairs of vertices that do not include a chosen universal vertex, and taking this number as the exponent of a power of two counts the number of graphs with the chosen vertices as universal.[12]
Starting from , these numbers of graphs are:
For , these numbers are odd when is even, and vice versa.[12] The unlabeled version of this graph enumeration problem is trivial, in the sense that the number of -vertex unlabeled graphs with a universal vertex is the same as the number of -vertex graphs.[13]
Recognition
In a graph with vertices, a universal vertex is a vertex whose degree is exactly .[10]
The property of having a universal vertex can be expressed by a formula in the first-order logic of graphs. Using to indicate the adjacency relation in a graph, a graph has a universal vertex if and only if it models the formula The existence of this formula, and its small number of alternations between
The property of having a universal vertex (or equivalently an isolated vertex) has been considered with respect to the
References
- MR 2059518.
- MR 2389013.
- MR 0172273.
- 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.
- ISBN 978-0-8176-8363-4
- MR 0166682
- ^ 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.
- ^ Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are friendship graphs of cardinal ", .
- MR 2901161.
- ^ MR 4607811
- MR 1285586
- ^ arXiv:cs/0205031
- ^ a b Sloane, N. J. A. (ed.), "Sequence A327367 (Number of labeled simple graphs with n vertices, at least one of which is isolated)", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
- S2CID 233169117