TOPICS
Search

Combinatorial Dual Graph


Let m(G) be the cycle rank of a graph G, m^*(G) be the cocycle rank, and the relative complement G-H of a subgraph H of G be defined as that subgraph obtained by deleting the lines of H. Then a graph G^* is a combinatorial dual of G if there is a one-to-one correspondence between their sets of lines such that for any choice Y and Y^* of corresponding subsets of lines,

 m^*(G-Y)=m^*(G)-m(<Y^*>),

where <Y^*> is the subgraph of G^* with the line set Y^*.

Whitney (1932) showed that the geometric dual graph and combinatorial dual graph are equivalent for planar graphs (Fleischner 1973; Harary 1994, p. 115), and so may simply be called "the" dual graph. Also, a graph is planar iff it has a combinatorial dual (Harary 1994, p. 115).


See also

Dual Graph, Geometric Dual Graph, Planar Graph

Explore with Wolfram|Alpha

References

Fleischner, H. "The Uniquely Embeddable Planar Graphs." Disc. Math. 4, 347-358, 1973.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 113-115, 1994.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Combinatorial Dual Graph

Cite this as:

Weisstein, Eric W. "Combinatorial Dual Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CombinatorialDualGraph.html

Subject classifications