Levi graph

Levi graph

infobox graph
name = Levi graph


image_caption = The Pappus graph, a Levi graph with 18 vertices formed from the Pappus configuration. Vertices labeled with single letters correspond to points in the configuration; vertices labeled with three letters correspond to lines through three points.
namesake =
vertices =
edges =
radius =
diameter =
girth = ≥ 6
chromatic_number =
chromatic_index =
properties =

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. The Levi graph of any system of points and lines 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. Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in Euclidean space. For every Levi graph, there is an equivalent hypergraph, 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 R3 as a 3×3×3 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 "Q"4 is the Levi graph of the Möbius configuration formed by the points and planes of two mutually incident tetrahedra.

References

* cite book
author = Levi, F. W.
title = Finite geometrical systems
year = 1942
publisher = Calcutta

*cite journal
title = Reductions of ("v"3) configurations
author = Boben, Marko
year = 2005
id = arxiv|archive=math.CO|id=0505136

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Levi (disambiguation) — Levi was, according to the Book of Genesis, the founder of the Israelite Tribe of Levi.Levi may also refer to: * The Laevi, or Levi, a Ligurian people in Gallia Transpadana * Levi II (fl. 3rd century), one of the amoraim * Levi (New Testament),… …   Wikipedia

  • Levi lemma — In mathematics, in the area of combinatorics, the Levi lemma states that, for all strings u , v , x and y , if uv = xy , then there exists a string w such that either: uw=x and v = wy or : u = xw and wv = y That is, there is a string w that is in …   Wikipedia

  • Desargues graph — Named after Gérard Desargues Vertices 20 Edges 30 …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Tutte–Coxeter graph — infobox graph name = Tutte–Coxeter graph image caption = namesake = W. T. Tutte H. S. M. Coxeter vertices = 30 edges = 45 girth = 8 chromatic number = 2 chromatic index = properties = Cubic Cage Moore graph Arc transitiveIn the mathematical field …   Wikipedia

  • Pappus graph — infobox graph name = Pappus graph image caption = The Pappus graph, a Levi graph with 18 vertices formed from the Pappus configuration. namesake = Pappus of Alexandria vertices = 18 edges = 27 chromatic number = chromatic index = properties =… …   Wikipedia

  • Nauru graph — The Nauru graph is Hamiltonian. Vertices 24 Edges 36 Radius 4 …   Wikipedia

  • Möbius–Kantor graph — Named after August Ferdinand Möbius and S. Kantor Vertices 16 …   Wikipedia

  • 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 sets U and V such that every edge connects a vertex in U to one in V ; that is, U and V are independent sets.… …   Wikipedia

  • Hypercube graph — The hypercube graph Q4 Vertices 2n Edges 2n−1n …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”