Universal vertex

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

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

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

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

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.

<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$ .

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

<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 the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

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 polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects.

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, 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.

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, 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, S2CID 233169117

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]