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.[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)}.
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]
References
- ↑ Sanders, Peter; Schulz, Christian (2013), "High quality graph partitioning", Graph partitioning and graph clustering, Contemp. Math., 588, Amer. Math. Soc., Providence, RI, pp. 1–17, MR 3074893, doi:10.1090/conm/588/11700.
- ↑ 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.
- ↑ Gardiner, A. (1974), "Antipodal covering graphs", Journal of Combinatorial Theory, Series B, 16: 255–273, MR 0340090, doi:10.1016/0095-8956(74)90072-0.
- ↑ 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, MR 1804713, doi:10.1016/S0166-218X(00)00220-1.