graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a quotient graph ''Q'' 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''. In other words, if ''G'' has edge set ''E'' and vertex set ''V'' and ''R'' is the

equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...

induced by the partition, then the quotient graph has vertex set ''V''/''R'' and edge set . More formally, a quotient graph is a quotient object in the

category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...

of graphs. The category of graphs is concretizable – mapping a graph to its set of vertices makes it a

concrete category In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category). This functor makes it possible to think of the objects of the category as sets with additional ...

– so its objects can be regarded as "sets with additional structure", and a quotient graph corresponds to the graph induced on the

quotient set In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...

''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 Condensation is the change of the state of matter from the gas phase into the liquid phase, and is the reverse of vaporization. The word most often refers to the water cycle. It can also be defined as the change in the state of water vapor ...

of a directed graph is the quotient graph where the

strongly connected component In the mathematics, mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachability, reachable from every other vertex. The strongly connected components of a directed graph form a partition of a s ...

s form the blocks of the partition. This construction can be used to derive a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...

from any directed graph. 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.

Computational complexity

Given an -vertex cubic graph ''G'' and a parameter , the computational complexity of determining whether ''G'' can be obtained as a quotient of a

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

with vertices is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

References

{{reflist5. Alain Bretto, Alain Faisant et François Hennecart, Elements of graph theory: From basic concept to moderne theory, European Mathematical Society Press, 2022. Graph operations Graph