quotient graph
In graph theory, 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.{{citation
| last1 = Sanders | first1 = Peter | author1-link = Peter Sanders (computer scientist)
| last2 = Schulz | first2 = Christian
| contribution = High quality graph partitioning
| doi = 10.1090/conm/588/11700
| mr = 3074893
| pages = 1–17
| publisher = Amer. Math. Soc., Providence, RI
| series = Contemp. Math.
| title = Graph partitioning and graph clustering
| volume = 588
| year = 2013| url = https://publikationen.bibliothek.kit.edu/1000035713/2677411 }}. 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.{{citation|journal=Formal Methods in System Design|date=January 2006|volume=28|issue=1|pages=37–56|title=An algorithm for strongly connected component analysis in n log n symbolic steps|first1=Roderick|last1=Bloem|first2=Harold N.|last2=Gabow|author2-link=Harold N. Gabow|first3=Fabio|last3=Somenzi|doi=10.1007/s10703-006-4341-z|s2cid=11747844 }}.
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.{{citation
| last = Gardiner | first = A.
| journal = Journal of Combinatorial Theory
| mr = 0340090
| pages = 255–273
| series = Series B
| title = Antipodal covering graphs
| volume = 16
| year = 1974
| issue = 3
| doi=10.1016/0095-8956(74)90072-0| doi-access = free
}}.
Computational complexity
Given an {{mvar|n}}-vertex cubic graph G and a parameter {{mvar|k}}, the computational complexity of determining whether G can be obtained as a quotient of a planar graph with {{math|n + k}} vertices is NP-complete.{{citation
| last1 = Faria | first1 = L.
| last2 = de Figueiredo | first2 = C. M. H.
| last3 = Mendonça | first3 = C. F. X.
| doi = 10.1016/S0166-218X(00)00220-1
| issue = 1–2
| journal = Discrete Applied Mathematics
| mr = 1804713
| pages = 65–83
| title = Splitting number is NP-complete
| volume = 108
| year = 2001| doi-access =
}}.
References
{{reflist}}5. Alain Bretto, Alain Faisant et François Hennecart, Elements of graph theory: From basic concept to moderne theory, European Mathematical Society Press, 2022.