Levi graph
From Wikipedia, the free encyclopedia
In combinatorics a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. 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 F. W. Levi, who wrote about them in 1942. Any Levi graph has girth at least six: there can be no 4-cycles, because that 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.
[edit] 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 Gray graph is the Levi graph of a configuration that can be realized in R3 as a 3×3×3 grid of 27 points and the 27 orthogonal lines through them.
- 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 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 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.
[edit] References
- Levi, F. W. (1942). Finite geometrical systems. Calcutta.
- Boben, Marko (2005). "Reductions of (v3) configurations". arXiv:math.CO/0505136.
[edit] External links
- Weisstein, Eric W., Levi Graph at MathWorld.
