595:
579:
33:
356:
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.
352:
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
415:
270:; 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).
322:
to its 15 edges, as described by
Coxeter (1958b), based on work by Sylvester (1844). Each vertex corresponds to an edge or a perfect matching, and connected vertices represent the
501:
538:
564:
442:
472:
594:
578:
192:
932:
730:
259:
341:, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The
366:
284:
372:
922:
622:
Brouwer, A. E.; Cohen, A. M.; and
Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
927:
477:
181:
937:
452:
84:
74:
517:
445:
277:
249:
177:
54:
881:
543:
843:
815:
803:
739:
420:
263:
229:
94:
8:
334:
323:
233:
165:
64:
819:
743:
831:
763:
755:
457:
353:
342:
338:
104:
890:
835:
767:
859:
823:
791:
747:
725:
711:
695:
648:
585:
311:
267:
118:
47:
908:
775:
669:
601:
330:
304:
241:
185:
173:
138:
128:
417:(there is an exceptional isomorphism between this group and the symmetric group
893:
315:
288:
827:
795:
916:
329:
Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a
221:
17:
864:
847:
751:
716:
699:
632:
292:
205:
148:
507:
vertices are either nonzero vectors, or isotropic 2-dimensional subspaces,
274:
237:
225:
201:
169:
161:
43:
451:
Concretely, the Tutte-Coxeter graph can be defined from a 4-dimensional
653:
636:
307:
245:
759:
898:
728:(1958b). "Twelve points in PG(5,3) with 95040 self-transformations".
780:"Elementary researches in the analysis of combinatorial aggregation"
779:
32:
345:
of this group correspond to permuting the six vertices of the
280:
are known. The Tutte–Coxeter is one of the 13 such graphs.
360:
444:). More specifically, it is the incidence graph of a
224:
with 30 vertices and 45 edges. As the unique smallest
546:
520:
480:
460:
423:
375:
888:
907:Exoo, G. "Rectilinear Drawings of Famous Graphs."
724:
694:
558:
532:
495:
466:
436:
409:
298:
914:
848:"The chords of the non-ruled quadric in PG(3,3)"
774:
700:"The chords of the non-ruled quadric in PG(3,3)"
879:
842:
802:
686:Master Thesis, University of Tübingen, 2018
510:there is an edge between a nonzero vector
863:
715:
652:
483:
394:
631:
514:and an isotropic 2-dimensional subspace
410:{\displaystyle Sp_{4}(\mathbb {F} _{2})}
670:"Rectilinear Drawings of Famous Graphs"
915:
806:(1947). "A family of cubical graphs".
889:
361:The Tutte–Coxeter graph as a building
684:Engineering Linear Layouts with SAT.
369:associated to the symplectic group
13:
731:Proceedings of the Royal Society A
14:
949:
873:
667:
604:of the Tutte–Coxeter graph is 3.
593:
588:of the Tutte–Coxeter graph is 2.
577:
496:{\displaystyle \mathbb {F} _{2}}
244:, and can be constructed as the
31:
303:The Tutte–Coxeter graph is the
299:Constructions and automorphisms
676:
661:
625:
616:
404:
389:
260:Cremona–Richmond configuration
193:Table of graphs and parameters
1:
609:
326:between edges and matchings.
882:"3D Model of Tutte's 8-cage"
262:). The graph is named after
7:
808:Proc. Cambridge Philos. Soc
10:
954:
570:
533:{\displaystyle W\subset V}
15:
933:Configurations (geometry)
828:10.1017/S0305004100023720
796:10.1080/14786444408644856
191:
157:
147:
137:
127:
117:
103:
93:
83:
73:
63:
53:
39:
30:
25:
637:"Crossing Number Graphs"
16:Not to be confused with
453:symplectic vector space
278:distance-regular graphs
865:10.4153/CJM-1958-046-3
752:10.1098/rspa.1958.0184
717:10.4153/CJM-1958-047-0
560:
559:{\displaystyle v\in W}
534:
497:
468:
446:generalized quadrangle
438:
411:
250:generalized quadrangle
218:Cremona–Richmond graph
561:
535:
498:
469:
439:
437:{\displaystyle S_{6}}
412:
544:
518:
478:
458:
421:
373:
264:William Thomas Tutte
820:1947PCPS...43..459T
744:1958RSPSA.247..279C
641:Mathematica Journal
635:; Exoo, G. (2009).
354:outer automorphisms
343:inner automorphisms
324:incidence structure
210:Tutte–Coxeter graph
182:Distance-transitive
26:Tutte–Coxeter graph
923:1958 introductions
891:Weisstein, Eric W.
880:François Labelle.
654:10.3888/tmj.11.2-2
556:
530:
493:
464:
434:
407:
367:spherical building
365:This graph is the
310:connecting the 15
928:Individual graphs
738:(1250): 279–293.
726:Coxeter, H. S. M.
696:Coxeter, H. S. M.
467:{\displaystyle V}
312:perfect matchings
198:
197:
945:
904:
903:
885:
869:
867:
839:
799:
776:Sylvester, J. J.
771:
721:
719:
687:
680:
674:
673:
665:
659:
658:
656:
629:
623:
620:
597:
586:chromatic number
581:
565:
563:
562:
557:
539:
537:
536:
531:
502:
500:
499:
494:
492:
491:
486:
473:
471:
470:
465:
443:
441:
440:
435:
433:
432:
416:
414:
413:
408:
403:
402:
397:
388:
387:
268:H. S. M. Coxeter
214:Tutte eight-cage
178:Distance-regular
119:Chromatic number
48:H. S. M. Coxeter
35:
23:
22:
953:
952:
948:
947:
946:
944:
943:
942:
913:
912:
876:
691:
690:
682:Wolz, Jessica;
681:
677:
666:
662:
630:
626:
621:
617:
612:
605:
602:chromatic index
598:
589:
582:
573:
545:
542:
541:
540:if and only if
519:
516:
515:
487:
482:
481:
479:
476:
475:
459:
456:
455:
428:
424:
422:
419:
418:
398:
393:
392:
383:
379:
374:
371:
370:
363:
351:
331:symmetric graph
321:
301:
285:crossing number
257:
184:
180:
176:
172:
168:
164:
129:Chromatic index
112:
46:
21:
12:
11:
5:
951:
941:
940:
938:Regular graphs
935:
930:
925:
911:
910:
905:
886:
875:
874:External links
872:
871:
870:
840:
814:(4): 459–474.
800:
772:
722:
689:
688:
675:
660:
624:
614:
613:
611:
608:
607:
606:
599:
592:
590:
583:
576:
572:
569:
568:
567:
555:
552:
549:
529:
526:
523:
508:
490:
485:
463:
431:
427:
406:
401:
396:
391:
386:
382:
378:
362:
359:
349:
319:
316:complete graph
314:of a 6-vertex
300:
297:
289:book thickness
258:(known as the
255:
196:
195:
189:
188:
159:
155:
154:
151:
145:
144:
141:
139:Book thickness
135:
134:
131:
125:
124:
121:
115:
114:
110:
107:
101:
100:
97:
91:
90:
87:
81:
80:
77:
71:
70:
67:
61:
60:
57:
51:
50:
41:
37:
36:
28:
27:
9:
6:
4:
3:
2:
950:
939:
936:
934:
931:
929:
926:
924:
921:
920:
918:
909:
906:
901:
900:
895:
892:
887:
883:
878:
877:
866:
861:
857:
853:
849:
845:
841:
837:
833:
829:
825:
821:
817:
813:
809:
805:
801:
797:
793:
789:
785:
781:
777:
773:
769:
765:
761:
757:
753:
749:
745:
741:
737:
733:
732:
727:
723:
718:
713:
709:
705:
701:
697:
693:
692:
685:
679:
671:
664:
655:
650:
646:
642:
638:
634:
628:
619:
615:
603:
596:
591:
587:
580:
575:
574:
553:
550:
547:
527:
524:
521:
513:
509:
506:
505:
504:
488:
461:
454:
449:
447:
429:
425:
399:
384:
380:
376:
368:
358:
355:
348:
344:
340:
339:automorphisms
336:
332:
327:
325:
317:
313:
309:
306:
296:
294:
290:
286:
281:
279:
276:
271:
269:
265:
261:
254:
251:
247:
243:
239:
235:
231:
227:
223:
222:regular graph
219:
215:
211:
207:
203:
194:
190:
187:
183:
179:
175:
171:
167:
163:
160:
156:
152:
150:
146:
142:
140:
136:
132:
130:
126:
122:
120:
116:
108:
106:
105:Automorphisms
102:
98:
96:
92:
88:
86:
82:
78:
76:
72:
68:
66:
62:
58:
56:
52:
49:
45:
42:
38:
34:
29:
24:
19:
18:Coxeter graph
897:
894:"Levi Graph"
855:
852:Can. J. Math
851:
844:Tutte, W. T.
811:
807:
804:Tutte, W. T.
787:
786:. Series 3.
783:
735:
729:
707:
704:Can. J. Math
703:
683:
678:
663:
644:
640:
627:
618:
511:
503:as follows:
450:
364:
346:
328:
302:
293:queue number
282:
272:
252:
217:
213:
209:
206:graph theory
202:mathematical
199:
149:Queue number
858:: 481–483.
790:: 285–295.
710:: 484–488.
633:Pegg, E. T.
333:; it has a
238:Moore graph
232:8, it is a
226:cubic graph
170:Moore graph
109:1440 (Aut(S
44:W. T. Tutte
40:Named after
917:Categories
610:References
308:Levi graph
246:Levi graph
158:Properties
899:MathWorld
836:123505185
784:Phil. Mag
768:121676627
698:(1958a).
668:Exoo, G.
551:∈
525:⊂
305:bipartite
242:bipartite
204:field of
186:Bipartite
174:Symmetric
846:(1958).
778:(1844).
337:of 1440
273:All the
240:. It is
85:Diameter
55:Vertices
816:Bibcode
740:Bibcode
571:Gallery
283:It has
248:of the
220:is a 3-
200:In the
834:
766:
760:100667
758:
291:3 and
236:and a
208:, the
75:Radius
832:S2CID
764:S2CID
756:JSTOR
647:(2).
474:over
335:group
275:cubic
230:girth
162:Cubic
95:Girth
65:Edges
600:The
584:The
287:13,
266:and
234:cage
166:Cage
860:doi
824:doi
792:doi
748:doi
736:247
712:doi
649:doi
295:2.
228:of
216:or
212:or
919::
896:.
856:10
854:.
850:.
830:.
822:.
812:43
810:.
788:24
782:.
762:.
754:.
746:.
734:.
708:10
706:.
702:.
645:11
643:.
639:.
448:.
113:))
69:45
59:30
902:.
884:.
868:.
862::
838:.
826::
818::
798:.
794::
770:.
750::
742::
720:.
714::
672:.
657:.
651::
566:.
554:W
548:v
528:V
522:W
512:v
489:2
484:F
462:V
430:6
426:S
405:)
400:2
395:F
390:(
385:4
381:p
377:S
350:6
347:K
320:6
318:K
256:2
253:W
153:2
143:3
133:3
123:2
111:6
99:8
89:4
79:4
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
