Universal vertex

Last updated June 24, 2024

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, and its universal vertex may be called the apex of the cone.^[1] This terminology should be distinguished from the unrelated usage of these words for universal quantifiers in the logic of graphs, and for apex graphs.

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 inclusion–exclusion, showing that there are an odd number of such graphs on any even number of vertices. This, in turn, can be used to show that the property of having a universal graph is evasive: testing this property may require checking the adjacency of all pairs of vertices. However, a universal vertex can be recognized immediately from its degree: in an $n$ -vertex graph, it has degree $n-1$ . Universal vertices can be described by a short logical formula, which has been used in graph algorithms for related properties.

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 friendship theorem of PaulErdő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.^[7] The assumption that the graph is finite is important; there exist infinite graphs in which every two vertices have one shared neighbor, but with no universal vertex.^[8]

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 $n$ -vertex dismantlable graphs that have a universal vertex tends to one in the limit as $n$ goes to infinity. The dismantlable graphs are also called cop-win graphs, because the side playing the cop wins a certain cop-and-robber game defined on these graphs.^[9]

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 $G\boxtimes H$ , the domination numbers $\gamma (G)$ and $\gamma (H)$ obey the inequalities $\max\{\gamma (G),\gamma (H)\}\leq \gamma (G\boxtimes H)\leq \gamma (G)\gamma (H).$ 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 labeled graphs with $n$ vertices, at least one of which is universal (or equivalently isolated, in the complement graph) can be counted by the inclusion–exclusion principle, in which one counts the graphs in which one chosen vertex is universal, then corrects for overcounting by subtracting the counts for graphs with two chosen universal vertices, then adding the counts for graphs with three chosen universal vertices, etc. This produces the formula

\displaystyle \sum _{k=1}^{n}(-1)^{k+1}{\binom {n}{k}}2^{\tbinom {n-k}{2}}.

In each term of the sum, $k$ is the number of vertices chosen to be universal, and ${\tbinom {n}{k}}$ is the number of ways to make this choice. ${\tbinom {n-k}{2}}$ 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 $n=1$ , these numbers of graphs are:

1, 1, 4, 23, 256, 5319, 209868, 15912975, 2343052576, 675360194287, ... (sequence A327367 in the OEIS).^[13]

For $n>1$ , these numbers are odd when $n$ is even, and vice versa.^[12] The unlabeled version of this graph enumeration problem is trivial, in the sense that the number of $n$ -vertex unlabeled graphs with a universal vertex is the same as the number of $(n-1)$ -vertex graphs.^[13]

Recognition

In a graph with $n$ vertices, a universal vertex is a vertex whose degree is exactly $n-1$ .^[10]

The property of having a universal vertex can be expressed by a formula in the first-order logic of graphs. Using $\sim$ to indicate the adjacency relation in a graph, a graph $G$ has a universal vertex if and only if it models the formula $\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 $k$ steps of removing a vertex from each component.^[14]

The property of having a universal vertex (or equivalently an isolated vertex) has been considered with respect to the Aanderaa–Karp–Rosenberg conjecture on how many queries (subroutine calls) are needed to test whether a labeled graph has a property, given access to the graph only through a subroutine that can test whether two given vertices are adjacent. In a graph with $n$ vertices, one can determine the entire graph, and test any property, using ${\tbinom {n}{2}}$ queries. A graph property is evasive if no algorithm can test the property guaranteeing fewer queries. Testing the existence of a universal vertex is evasive, on graphs with an even number of vertices. There are an odd number of these graphs that have a universal vertex. A testing algorithm can be forced to query all pairs of vertices by an adjacency subroutine that always answers in such a way as to leave an odd number of remaining graphs that have a universal vertex. Until all edges are tested, the total number of remaining graphs will be even, so the algorithm will be unable to determine whether the graph it is querying has a universal vertex.^[12]

Related Research Articles

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.

In mathematics, an abstract polytope is an algebraic partially ordered set which captures the dyadic property of a traditional polytope without specifying purely geometric properties such as points and lines.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $-dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.$

<span class="mw-page-title-main">Cartesian product of graphs</span> Operation in graph theory

In graph theory, the Cartesian product $G □ H$ of graphs $G$ and $H$ is a graph such that:

Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a possibly-empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing (1968), and states that, if $γ(G)$ denotes the minimum number of vertices in a dominating set for the graph $G$ , then

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex $and vertex ?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer. A property satisfying this conjecture is called evasive.$

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, γ_∞(G), is the minimum number of vertices possible in the initial set D. For example, the eternal domination number of the cycle on five vertices is two.

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets.

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

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, 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 .
↑ 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 .
↑ 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.
↑ 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
↑ Klee, Victor (1964), "On the number of vertices of a convex polytope", Canadian Journal of Mathematics, 16: 701–720, doi:10.4153/CJM-1964-067-6, 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 $\scriptstyle 2^{\aleph _{\alpha }}$ friendship graphs of cardinal $\scriptstyle \aleph _{\alpha }$ ", Canadian Mathematical Bulletin , 19 (4): 431–433, doi: 10.4153/cmb-1976-064-1 .
↑ 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 .
1 2 Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (2023), Domination in Graphs: Core Concepts, Springer Monographs in Mathematics, Springer, Cham, p. 2, doi:10.1007/978-3-031-09496-5, ISBN 978-3-031-09495-8, MR 4607811
↑ Fisher, David C. (1994), "Domination, fractional domination, 2-packing, and graph products", SIAM Journal on Discrete Mathematics, 7 (3): 493–498, doi:10.1137/S0895480191217806, MR 1285586
1 2 3 Lovász, László; Young, Neal E. (2002), "Lecture Notes on Evasiveness of Graph Properties", arXiv: cs/0205031
1 2 Sloane, N. J. A. (ed.), "SequenceA327367(Number of labeled simple graphs with n vertices, at least one of which is isolated)", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation
↑ 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, ISBN 978-1-6654-4895-6, S2CID 233169117

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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] 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 .

[4] 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.

[5] 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

[6] Klee, Victor (1964), "On the number of vertices of a convex polytope", Canadian Journal of Mathematics, 16: 701–720, doi:10.4153/CJM-1964-067-6, MR 0166682

[7] 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.

[8] Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are $\scriptstyle 2^{\aleph _{\alpha }}$ friendship graphs of cardinal $\scriptstyle \aleph _{\alpha }$ ", Canadian Mathematical Bulletin , 19 (4): 431–433, doi: 10.4153/cmb-1976-064-1 .

[9] 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 .

[h3-10] 1 2 Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (2023), Domination in Graphs: Core Concepts, Springer Monographs in Mathematics, Springer, Cham, p. 2, doi:10.1007/978-3-031-09496-5, ISBN 978-3-031-09495-8, MR 4607811

[11] Fisher, David C. (1994), "Domination, fractional domination, 2-packing, and graph products", SIAM Journal on Discrete Mathematics, 7 (3): 493–498, doi:10.1137/S0895480191217806, MR 1285586

[evasiveness-12] 1 2 3 Lovász, László; Young, Neal E. (2002), "Lecture Notes on Evasiveness of Graph Properties", arXiv: cs/0205031

[oeis-13] 1 2 Sloane, N. J. A. (ed.), "SequenceA327367(Number of labeled simple graphs with n vertices, at least one of which is isolated)", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation

[14] 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, ISBN 978-1-6654-4895-6, S2CID 233169117

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]