Tutte–Coxeter graph

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-transitive

In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8 it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle "W"2. The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a).

Duads, synthemes, and automorphisms

A particularly simple combinatorial construction of the Tutte-Coxeter graph is due to Coxeter (1958b), based on much earlier work by Sylvester (1844). From a set of six elements (for instance the letters a,b,c,d,e,f) Sylvester defined a "duad" to be one of the 15 unordered pairs of elements: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, or ef. He also defined a "syntheme" to be one of the 15 partitions of the elements into three duads: (ab,cd,ef), (ab,ce,df), etc. Each syntheme contains three duads, and each duad belongs to three synthemes. The Tutte-Coxeter graph can be viewed as having one vertex per duad, one vertex per syntheme, and an edge connecting each syntheme to each of the three duads that form it.

Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph; it has a group of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six elements from which we defined the morphemes and synthemes; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the outer automorphisms of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte-Coxeter graph is equivalent to any other such path by one such automorphism.

References

*cite journal
author = Coxeter, H. S. M.
authorlink = H. S. M. Coxeter
title = The chords of the non-ruled quadric in PG(3,3)
journal = Canad. J. Math.
volume = 10
year = 1958a
pages = 484–488

*cite journal
author = Coxeter, H. S. M.
authorlink = H. S. M. Coxeter
title = Twelve points in PG(5,3) with 95040 self-transformations
journal = Proc. Roy. Soc. London. Ser. A
volume = 247
year = 1958b
url = http://www.jstor.org/stable/100667
pages = 279–293

*cite journal
author = Sylvester, J. J.
authorlink = J. J. Sylvester
title = Elementary researches in the analysis of combinatorial aggregation
journal = The Philos. Mag., Series 3
volume = 24
year = 1844
pages = 285–295

*cite journal
author = Tutte, W. T.
authorlink = William Thomas Tutte
title = A family of cubical graphs
journal = Proc. Cambridge Philos. Soc.
volume = 43
year = 1947
pages = 459–474

*cite journal
author = Tutte, W. T.
authorlink = William Thomas Tutte
title = The chords of the non-ruled quadric in PG(3,3)
journal = Canad. J. Math.
volume = 10
year = 1958
pages = 481–483

External links

*
* [http://sma.uni.lu/bisdorff/RubyDataSets/Tuttes8cage.html Ruby Data set: The Tutte-Coxeter (Levi) graph]
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Graphe de Tutte–Coxeter — Représentation hamiltonienne du graphe de Tutte–Coxeter. Nombre de sommets 30 Nombre d arêtes 45 Distribution des degrés 3 régulier Rayo …   Wikipédia en Français

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Distance-transitive graph — The Biggs Smith graph, the largest 3 regular distance transitive graph. Graph families defined by their automorphisms distance transitive …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • Cage (graph theory) — In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an ( r , g ) graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest… …   Wikipedia

  • Harold Scott MacDonald Coxeter — H. S. M. Donald Coxeter Born February 9, 1907(1907 02 09) London, England …   Wikipedia

  • Moore graph — Unsolved problems in mathematics Does a Moore graph with girth 5 and degree 57 exist? In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

Share the article and excerpts

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