“Tutte–Coxeter graph”的意思、由来-开放百科全书

词条

Tutte–Coxeter graph

释义

Constructions and automorphisms
The Tutte–Coxeter graph as a building
Gallery
References
External links

{{Distinguish|Coxeter graph}}{{infobox graph
| name = Tutte–Coxeter graph
| image =
| image_caption =
| namesake = W. T. Tutte
H. S. M. Coxeter
| vertices = 30
| edges = 45
| diameter = 4
| radius = 4
| automorphisms = 1440 (Aut(S₆))
| girth = 8
| chromatic_number = 2
| chromatic_index = 3
| properties = Cubic
Cage
Moore graph
Symmetric
Distance-regular
Distance-transitive
Bipartite
|book thickness=3|queue number=2}}

In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph 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₂ (known as the Cremona–Richmond configuration). 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).

All the cubic distance-regular graphs are known.^[1] The Tutte–Coxeter is one of the 13 such graphs.

It has book thickness 3 and queue number 2.^[2]

Constructions and automorphisms

A particularly simple combinatorial construction of the Tutte–Coxeter graph is due to Coxeter (1958b), based on work by Sylvester (1844). In modern terminology, take a complete graph on 6 vertices K₆. It has 15 edges and also 15 perfect matchings. Each vertex of the Tutte–Coxeter graph corresponds to an edge or perfect matching of the K₆, and each edge of the Tutte–Coxeter graph connects a perfect matching of the K₆ to each of its three component edges. By symmetry, each edge of the K₆ belongs to three perfect matchings. Incidentally, this partitioning of vertices into edge-vertices and matching-vertices shows that the Tutte-Coxeter graph is bipartite.

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 vertices of the K₆ graph; 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.

The Tutte–Coxeter graph as a building

This graph is the spherical building associated to the symplectic group (and there is an exceptional isomorphism between this group and the symmetric group ). More specifically, it is the incidence graph of a generalized quadrangle.

Gallery

References

1. ^Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
2. ^Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018

{{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 = Can. J. Math.
| volume = 10
| year = 1958a
| pages = 484–488
| doi = 10.4153/CJM-1958-047-0}}

{{cite journal

| author = Coxeter, H. S. M.
| authorlink = H. S. M. Coxeter
| title = Twelve points in PG(5,3) with 95040 self-transformations
| journal = Proceedings of the Royal Society A
| volume = 247
| year = 1958b
| issue = 1250
| pages = 279–293
| jstor = 100667
| doi = 10.1098/rspa.1958.0184}}

{{cite journal

| author = Sylvester, J. J.
| authorlink = J. J. Sylvester
| title = Elementary researches in the analysis of combinatorial aggregation
| journal = Phil. Mag.
| series = 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
| doi = 10.1017/S0305004100023720
| issue = 4}}

{{cite journal

| author = Tutte, W. T.
| authorlink = William Thomas Tutte
| title = The chords of the non-ruled quadric in PG(3,3)
| journal = Can. J. Math.
| volume = 10
| year = 1958
| pages = 481–483
| doi = 10.4153/CJM-1958-046-3}}

External links

{{cite web | author = François Labelle | title = 3D Model of Tutte's 8-cage | url = http://www.cs.berkeley.edu/~flab/proto/report/report.html}}
{{MathWorld|urlname=LeviGraph|title=Levi Graph}}
Exoo, G. "Rectilinear Drawings of Famous Graphs."

4 : 1958 introductions|Individual graphs|Configurations|Regular graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。