Quotient graph

Last updated August 19, 2023

In graph theory, a quotient graphQ of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G.^[1] In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]_R, [v]_R) | (u, v) ∈ E(G)}.

More formally, a quotient graph is a quotient object in the category of graphs. The category of graphs is concretizable – mapping a graph to its set of vertices makes it a concrete category – so its objects can be regarded as "sets with additional structure", and a quotient graph corresponds to the graph induced on the quotient set V/R of its vertex set V. Further, there is a graph homomorphism (a quotient map) from a graph to a quotient graph, sending each vertex or edge to the equivalence class that it belongs to. Intuitively, this corresponds to "gluing together" (formally, "identifying") vertices and edges of the graph.

Examples

A graph is trivially a quotient graph of itself (each block of the partition is a single vertex), and the graph consisting of a single point is the quotient graph of any non-empty graph (the partition consisting of a single block of all vertices). The simplest non-trivial quotient graph is one obtained by identifying two vertices (vertex identification); if the vertices are connected, this is called edge contraction.

Special types of quotient

The condensation of a directed graph is the quotient graph where the strongly connected components form the blocks of the partition. This construction can be used to derive a directed acyclic graph from any directed graph.^[2]

The result of one or more edge contractions in an undirected graph G is a quotient of G, in which the blocks are the connected components of the subgraph of G formed by the contracted edges. However, for quotients more generally, the blocks of the partition giving rise to the quotient do not need to form connected subgraphs.

If G is a covering graph of another graph H, then H is a quotient graph of G. The blocks of the corresponding partition are the inverse images of the vertices of H under the covering map. However, covering maps have an additional requirement that is not true more generally of quotients, that the map be a local isomorphism.^[3]

Computational complexity

It is NP-complete, given an $n$ -vertex cubic graph G and a parameter $k$ , to determine whether G can be obtained as a quotient of a planar graph with $n + k$ vertices.^[4]

Related Research Articles

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

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 field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

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 the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In the mathematical field of graph theory, a transitive reduction of a directed graph $D$ is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices $v$ , $w$ a (directed) path from $v$ to $w$ in $D$ exists if and only if such a path exists in the reduction. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.

<span class="mw-page-title-main">Biconnected component</span> Maximal biconnected subgraph

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

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.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

References

↑ Sanders, Peter; Schulz, Christian (2013), "High quality graph partitioning", Graph partitioning and graph clustering, Contemp. Math., vol. 588, Amer. Math. Soc., Providence, RI, pp. 1–17, doi:10.1090/conm/588/11700, MR 3074893 .
↑ Bloem, Roderick; Gabow, Harold N.; Somenzi, Fabio (January 2006), "An algorithm for strongly connected component analysis in n log n symbolic steps", Formal Methods in System Design, 28 (1): 37–56, doi:10.1007/s10703-006-4341-z, S2CID 11747844 .
↑ Gardiner, A. (1974), "Antipodal covering graphs", Journal of Combinatorial Theory, Series B, 16 (3): 255–273, doi: 10.1016/0095-8956(74)90072-0 , MR 0340090 .
↑ Faria, L.; de Figueiredo, C. M. H.; Mendonça, C. F. X. (2001), "Splitting number is NP-complete", Discrete Applied Mathematics , 108 (1–2): 65–83, doi:10.1016/S0166-218X(00)00220-1, MR 1804713 .

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] Sanders, Peter; Schulz, Christian (2013), "High quality graph partitioning", Graph partitioning and graph clustering, Contemp. Math., vol. 588, Amer. Math. Soc., Providence, RI, pp. 1–17, doi:10.1090/conm/588/11700, MR 3074893 .

[2] Bloem, Roderick; Gabow, Harold N.; Somenzi, Fabio (January 2006), "An algorithm for strongly connected component analysis in n log n symbolic steps", Formal Methods in System Design, 28 (1): 37–56, doi:10.1007/s10703-006-4341-z, S2CID 11747844 .

[3] Gardiner, A. (1974), "Antipodal covering graphs", Journal of Combinatorial Theory, Series B, 16 (3): 255–273, doi: 10.1016/0095-8956(74)90072-0 , MR 0340090 .

[4] Faria, L.; de Figueiredo, C. M. H.; Mendonça, C. F. X. (2001), "Splitting number is NP-complete", Discrete Applied Mathematics , 108 (1–2): 65–83, doi:10.1016/S0166-218X(00)00220-1, MR 1804713 .

[1]

[2]

[3]

[4]