1. Examples

2. Special types of quotient

3. Computational complexity

4. References

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

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 {{mvar|n}}-vertex cubic graph G and a parameter {{mvar|k}}, to determine whether G can be obtained as a quotient of a planar graph with {{math|n + k}} vertices.^[4]

References

• Lockheed FO Lightning
• Lockheed FV Salmon
• Lockheed GV
• Lockheed H-51
• Lockheed HC-130 Hercules
• Lockheed High Virgo
• Lockheed Jetsar
• Lockheed Jetsars
• Lockheed JO Electra Junior
• Lockheed KC-130
• Lockheed KXL1
• Lockheed L-10
• Lockheed L-1000
• Lockheed L-100-30 Hercules
• Lockheed -L1011
• Lockheed L1011
• Lockheed L-1011
• Lockheed L-1011-100
• Lockheed L-1011-250
• Lockheed L1011-385-1
• Lockheed L1011-500
• Lockheed L-1011 operators
• Lockheed L-10 Electra
• Lockheed L-12 Electra Junior
• Lockheed L-133