In
combinatorial mathematics, a Levi graph or incidence graph is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
associated with an
incidence structure.
[. See in particula]
p. 181
From a collection of points and lines in an
incidence geometry or a
projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for
Friedrich Wilhelm Levi, who wrote about them in 1942.
The Levi graph of a system of points and lines usually has
girth at least six: Any 4-
cycles would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure.
Levi graphs of configurations are
biregular, and every biregular graph with girth at least six can be viewed as the Levi graph of an abstract configuration.
[.]
Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...
. For every Levi graph, there is an equivalent
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) ...
, and vice versa.
Examples
* The
Desargues graph is the Levi graph of the
Desargues configuration, composed of 10 points and 10 lines. There are 3 points on each line, and 3 lines passing through each point. The Desargues graph can also be viewed as the
generalized Petersen graph G(10,3) or the
bipartite Kneser graph with parameters 5,2. It is 3-regular with 20 vertices.
* The
Heawood graph is the Levi graph of the
Fano plane. It is also known as the (3,6)-
cage, and is 3-regular with 14 vertices.
* The
Möbius–Kantor graph is the Levi graph of the
Möbius–Kantor configuration, a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. It is 3-regular with 16 vertices.
* The
Pappus graph is the Levi graph of the
Pappus configuration, composed of 9 points and 9 lines. Like the Desargues configuration there are 3 points on each line and 3 lines passing through each point. It is 3-regular with 18 vertices.
* The
Gray graph is the Levi graph of a configuration that can be realized in
as a
grid of 27 points and the 27 orthogonal lines through them.
* The
Tutte eight-cage is the Levi graph of the
Cremona–Richmond configuration. It is also known as the (3,8)-cage, and is 3-regular with 30 vertices.
* The four-dimensional
hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, e ...
is the Levi graph of the
Möbius configuration formed by the points and planes of two mutually incident tetrahedra.
* The
Ljubljana graph on 112 vertices is the Levi graph of the Ljubljana configuration.
[.]
References
External links
*
{{Incidence structures
Families of sets
Configurations (geometry)
Geometric graphs