Let denote a configuration
with points and lines ("blocks") . Then the Levi graph , also called the incidence graph, of a configuration
is a bipartite graph with "black" vertices
, "white" vertices , and an edge between and iff (Coxeter 1950, Pisanski and Randić 2000).
The Levi graph of a symmetric configuration is a -regular bipartite graph
on vertices and edges. Configurations with the same parameters need not have
isomorphic Levi graphs. For example, the Bokowski-Schewe
graph and Bokowski-Pilaud graph are
nonisomorphic and have automorphism group orders
48 and 4, respectively (Bokowski and Pilaud 2014). Similarly, the Grünbaum-Rigby
graph and Berman-Gévay-Pisanski
graph are nonisomorphic and have automorphism group orders 672 and 12, respectively
(Berman et al. 2024).
Dual configurations have the same Levi graph, with the roles of the white and black vertices interchanged.
The following table summarizes the Levi graphs of some named configurations.
Berman, L. W.; Gévay, G.; and Pisanski, T. "On a New ()
Polycyclic Configuration." Electron. J. Combin.31, #P4.54, 2024.
https://doi.org/10.37236/12405.Berman,
L. W.; Gévay, G.; and Pisanski, T. "Polycyclic Geometric Realizations
of the Gray Configuration." 20 Feb 2025. https://arxiv.org/abs/2502.14484.Bokowski,
J. and Pilaud, V. "Enumerating Topological -Configurations." Comput. Geom.47,
175-186, 2014. https://doi.org/10.1016/j.comgeo.2012.10.002.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.Grünbaum,
B. "Musings on an Example of Danzer's." Europ. J. Combin.29,
1910-1918, 2008. https://doi.org/10.1016/j.ejc.2008.01.004.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.
denote a configuration
with 
points 
and 
lines ("blocks") 
. Then the Levi graph 
, also called the incidence graph, of a configuration
is a bipartite graph with "black" vertices
, "white" vertices 
, and an edge between 
and 
iff 
(Coxeter 1950, Pisanski and Randić 2000).
configuration is a 
-regular bipartite graph
on 
vertices and 
edges. Configurations with the same parameters need not have
isomorphic Levi graphs. For example, the Bokowski-Schewe
graph and Bokowski-Pilaud graph are
nonisomorphic and have automorphism group orders
48 and 4, respectively (Bokowski and Pilaud 2014). Similarly, the Grünbaum-Rigby
graph and Berman-Gévay-Pisanski
graph are nonisomorphic and have automorphism group orders 672 and 12, respectively
(Berman et al. 2024).
)
Polycyclic Configuration." Electron. J. Combin. 31, #P4.54, 2024.
-Configurations." Comput. Geom. 47,
175-186, 2014.