TOPICS
Search

Levi Graph


Let (P,B) denote a configuration with v points P={p_1,...,p_v} and b lines ("blocks") B=(B_1,...,B_b). Then the Levi graph L(P,B), also called the incidence graph, of a configuration is a bipartite graph with "black" vertices P, "white" vertices B, and an edge between p_i in P and B_j in B iff p_i in B_j (Coxeter 1950, Pisanski and Randić 2000).

The following table summarizes the Levi graphs of some common configurations.

Dual configurations have the same incidence graph, but with the roles of the white and black vertices interchanged.


See also

Configuration, Menger Graph

Explore with Wolfram|Alpha

References

Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Godsil, C. and Royle, G. "Incidence Graphs." §5.1 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 78-79, 2001.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.

Cite this as:

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

Subject classifications