Universal vertex

Last updated

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

Contents

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

Other properties

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.

Related Research Articles

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

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 the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is called a planar matroid; these are exactly the graphic matroids formed from planar graphs.

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

Degree (graph theory) Number of edges incident to a given vertex in a node-link graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

Connectivity (graph theory) Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the Series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

Rado graph infinite graph containing all countable 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 (1937). 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.

Split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

  1. Addition of a single isolated vertex to the graph.
  2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.
Pseudoforest

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

Distance-hereditary graph

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

Halin graph

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

Clebsch graph

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit-evasion game in which he chases a robber, the players alternately moving along an edge of a graph or staying 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.

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, 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: 789–795, doi: 10.2307/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, 1, Amsterdam: North-Holland, pp. 145–162.
  5. 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 .