840:
828:
856:
29:
274:, and connect the other ten vertices into a ten-pointed star that connects pairs of vertices at distance three in a second decagon. The Desargues graph consists of the 20 edges of these two polygons together with an additional 10 edges connecting points of one decagon to the corresponding points of the other.
393:
One can interpret this product representation of the symmetry group in terms of the constructions of the
Desargues graph: the symmetric group on five points is the symmetry group of the Desargues configuration, and the order-2 subgroup swaps the roles of the vertices that represent points of the
398:, the symmetric group on five points acts separately on the two-element and three-element subsets of the five points, and complementation of subsets forms a group of order two that transforms one type of subset into the other. The symmetric group on five points is also the symmetry group of the
323:. Its vertices can be labeled by the ten two-element subsets and the ten three-element subsets of a five-element set, with an edge connecting two vertices when one of the corresponding sets is a subset of the other. Equivalently, the Desargues graph is the
368:
is
Hamiltonian, the Hamiltonicity of the Desargues graph is no surprise. (It also follows from the stronger conjecture of Lovász that except for a few known counter-examples, all vertex-transitive graphs have Hamiltonian
686:
289:, their center of perspectivity, and their axis of perspectivity. The Desargues graph has one vertex for each point, one vertex for each line, and one edge for every incident point-line pair.
839:
746:
827:
855:
193:
552:
382:: it has symmetries that take any vertex to any other vertex and any edge to any other edge. Its symmetry group has order 240, and is
308:, formed by replacing each Petersen graph vertex by a pair of vertices and each Petersen graph edge by a pair of crossed edges.
297:, describes a set of points and lines forming this configuration, and the configuration and the graph take their name from it.
1040:
736:
813:
used this diagram to show the combination product sets (CPS) of the 3 out of 6 set. He called this
Structure the Eikosany.
990:
Balaban, A. T.; FÇŽrcaĹźiu, D.; BÇŽnicÇŽ, R. (1966), "Graphs of multiple 1, 2-shifts in carbonium ions and related systems",
489:. So the Desargues graph is one of only seven symmetric Generalized Petersen graphs. Among these seven graphs are the
510:
402:, and the order-2 subgroup swaps the vertices within each pair of vertices formed in the double cover construction.
1148:
804:
261:
1038:
KlavĹľar, Sandi; Lipovec, Alenka (2003), "Partial cubes as subdivision graphs and as generalized
Petersen graphs",
543:
214:
769:
229:, arises from several different combinatorial constructions, has a high level of symmetry, is the only known
1153:
421:
282:
76:
66:
794:
773:
395:
301:
286:
174:
696:
450:
222:
46:
290:
956:
765:
86:
240:
The name "Desargues graph" has also been used to refer to a ten-vertex graph, the complement of the
294:
56:
39:
972:
926:
96:
1012:(1970), "Role of pseudorotation in the stereochemistry of nucleophilic displacement reactions",
1125:
885:
776:
394:
Desargues configuration and the vertices that represent lines. Alternatively, in terms of the
383:
331:
178:
1117:
1049:
1021:
964:
918:
862:
757:
324:
226:
117:
1083:; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
1080:
846:
761:
387:
379:
186:
182:
147:
137:
127:
947:; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs",
960:
780:
724:
692:
500:
399:
305:
245:
241:
1054:
270:. To form the Desargues graph in this way, connect ten of the vertices into a regular
1142:
976:
339:
889:
814:
784:
750:
716:
520:
335:
327:
of the 5-dimensional hypercube determined by the vertices of weight 2 and weight 3.
312:
234:
230:
206:
157:
1009:
801:
791:
530:
218:
202:
170:
968:
810:
278:
1129:
739: 6, and is the smallest cubic graph with that crossing number (sequence
944:
894:
723:
compounds. In this application, the thirty edges of the graph correspond to
708:
28:
285:. This configuration consists of ten points and ten lines describing two
1025:
1121:
930:
909:
Kagno, I. N. (1947), "Desargues' and Pappus' graphs and their groups",
271:
256:
There are several different ways of constructing the
Desargues graph:
720:
922:
807:
in the non-orientable manifold of genus 6, with decagonal faces.
681:{\displaystyle (x-3)(x-2)^{4}(x-1)^{5}(x+1)^{5}(x+2)^{4}(x+3).\,}
490:
797:
are known. The
Desargues graph is one of the 13 such graphs.
741:
16:
Distance-transitive cubic graph with 20 nodes and 30 edges
357:-dimensional hypercube induced by the vertices of weight
1093:
McMullen, Peter (1992), "The regular polyhedra of type
555:
833:
Desargues graph colored to highlight various cycles.
166:
156:
146:
136:
126:
116:
95:
85:
75:
65:
55:
45:
35:
21:
949:Proceedings of the Cambridge Philosophical Society
917:(4), The Johns Hopkins University Press: 859–863,
680:
815:https://www.anaphoria.com/eikosanystructures.pdf
293:, named after 17th-century French mathematician
800:The Desargues graph can be embedded as a self-
237:, and has been applied in chemical databases.
8:
1071:Master Thesis, University of TĂĽbingen, 2018
1053:
677:
653:
631:
609:
587:
554:
749:). It is the only known nonplanar cubic
876:
823:
711:, the Desargues graph is known as the
18:
691:Therefore, the Desargues graph is an
390:on 5 points with a group of order 2.
7:
1069:Engineering Linear Layouts with SAT.
715:; it is used to organize systems of
453:only in the following seven cases:
248:of the 20-vertex Desargues graph.
244:, which can also be formed as the
14:
865:of the Desargues graph is 2.
849:of the Desargues graph is 3.
854:
838:
826:
334:and can be constructed from the
225:and 30 edges. It is named after
27:
911:American Journal of Mathematics
699:consists entirely of integers.
405:The generalized Petersen graph
671:
659:
650:
637:
628:
615:
606:
593:
584:
571:
568:
556:
194:Table of graphs and parameters
1:
1055:10.1016/S0012-365X(02)00575-7
764:3, radius 5, diameter 5 and
737:rectilinear crossing number
1170:
546:of the Desargues graph is
262:generalized Petersen graph
969:10.1017/S0305004100049811
544:characteristic polynomial
378:The Desargues graph is a
192:
26:
756:The Desargues graph has
735:The Desargues graph has
795:distance-regular graphs
330:The Desargues graph is
283:Desargues configuration
682:
396:bipartite Kneser graph
349:, the subgraph of the
313:bipartite Kneser graph
302:bipartite double cover
683:
342:conjectured that for
287:perspective triangles
1110:Geometricae Dedicata
1041:Discrete Mathematics
713:Desargues–Levi graph
553:
386:to the product of a
374:Algebraic properties
1026:10.1021/ar50034a001
961:1971PCPS...70..211F
511:Möbius–Kantor graph
215:distance-transitive
1122:10.1007/BF00151518
886:Weisstein, Eric W.
768:6. It is also a 3-
678:
521:dodecahedral graph
291:Desargues' theorem
1149:Individual graphs
890:"Desargues Graph"
777:Hamiltonian graph
422:vertex-transitive
199:
198:
1161:
1133:
1132:
1107:
1106:
1100:
1098:
1090:
1084:
1078:
1072:
1065:
1059:
1058:
1057:
1048:(1–3): 157–165,
1035:
1029:
1028:
1006:
1000:
999:
992:Rev. Roum. Chim.
987:
981:
979:
941:
935:
933:
906:
900:
899:
898:
881:
863:chromatic number
858:
842:
830:
770:vertex-connected
758:chromatic number
744:
731:Other properties
727:of the ligands.
687:
685:
684:
679:
658:
657:
636:
635:
614:
613:
592:
591:
538:
528:
518:
508:
498:
488:
484:
480:
476:
472:
468:
464:
448:
437:
430:
419:
367:
360:
356:
348:
325:induced subgraph
322:
295:GĂ©rard Desargues
269:
227:Girard Desargues
175:Distance-regular
118:Chromatic number
111:
40:GĂ©rard Desargues
31:
19:
1169:
1168:
1164:
1163:
1162:
1160:
1159:
1158:
1139:
1138:
1137:
1136:
1104:
1102:
1096:
1094:
1092:
1091:
1087:
1079:
1075:
1067:Wolz, Jessica,
1066:
1062:
1037:
1036:
1032:
1020:(10): 321–331,
1014:Acc. Chem. Res.
1008:
1007:
1003:
989:
988:
984:
943:
942:
938:
923:10.2307/2371806
908:
907:
903:
884:
883:
882:
878:
873:
866:
859:
850:
847:chromatic index
843:
834:
831:
822:
762:chromatic index
740:
733:
725:pseudorotations
705:
649:
627:
605:
583:
551:
550:
533:
523:
513:
503:
493:
486:
482:
478:
474:
470:
466:
454:
451:edge-transitive
439:
432:
425:
424:if and only if
406:
388:symmetric group
380:symmetric graph
376:
362:
358:
350:
343:
321:
315:
264:
254:
211:Desargues graph
185:
181:
177:
173:
128:Chromatic index
110:
106:
102:
22:Desargues graph
17:
12:
11:
5:
1167:
1165:
1157:
1156:
1154:Regular graphs
1151:
1141:
1140:
1135:
1134:
1085:
1081:Brouwer, A. E.
1073:
1060:
1030:
1001:
982:
955:(2): 211–218,
936:
901:
875:
874:
872:
869:
868:
867:
860:
853:
851:
844:
837:
835:
832:
825:
821:
818:
781:book thickness
774:edge-connected
732:
729:
704:
701:
693:integral graph
689:
688:
676:
673:
670:
667:
664:
661:
656:
652:
648:
645:
642:
639:
634:
630:
626:
623:
620:
617:
612:
608:
604:
601:
598:
595:
590:
586:
582:
579:
576:
573:
570:
567:
564:
561:
558:
501:Petersen graph
400:Petersen graph
375:
372:
371:
370:
328:
319:
309:
306:Petersen graph
298:
275:
253:
250:
246:bipartite half
242:Petersen graph
197:
196:
190:
189:
168:
164:
163:
160:
154:
153:
150:
148:Book thickness
144:
143:
140:
134:
133:
130:
124:
123:
120:
114:
113:
108:
104:
99:
93:
92:
89:
83:
82:
79:
73:
72:
69:
63:
62:
59:
53:
52:
49:
43:
42:
37:
33:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1166:
1155:
1152:
1150:
1147:
1146:
1144:
1131:
1127:
1123:
1119:
1115:
1111:
1089:
1086:
1082:
1077:
1074:
1070:
1064:
1061:
1056:
1051:
1047:
1043:
1042:
1034:
1031:
1027:
1023:
1019:
1015:
1011:
1005:
1002:
997:
993:
986:
983:
978:
974:
970:
966:
962:
958:
954:
950:
946:
940:
937:
932:
928:
924:
920:
916:
912:
905:
902:
897:
896:
891:
887:
880:
877:
870:
864:
857:
852:
848:
841:
836:
829:
824:
819:
817:
816:
812:
808:
806:
803:
798:
796:
793:
788:
786:
782:
778:
775:
771:
767:
763:
759:
754:
752:
748:
743:
738:
730:
728:
726:
722:
718:
717:stereoisomers
714:
710:
702:
700:
698:
694:
674:
668:
665:
662:
654:
646:
643:
640:
632:
624:
621:
618:
610:
602:
599:
596:
588:
580:
577:
574:
565:
562:
559:
549:
548:
547:
545:
540:
536:
532:
526:
522:
516:
512:
506:
502:
496:
492:
491:cubical graph
462:
458:
452:
446:
442:
435:
428:
423:
417:
413:
409:
403:
401:
397:
391:
389:
385:
381:
373:
365:
354:
346:
341:
337:
333:
329:
326:
318:
314:
310:
307:
303:
299:
296:
292:
288:
284:
280:
276:
273:
267:
263:
259:
258:
257:
252:Constructions
251:
249:
247:
243:
238:
236:
232:
228:
224:
220:
216:
212:
208:
204:
195:
191:
188:
184:
180:
176:
172:
169:
165:
161:
159:
155:
151:
149:
145:
141:
139:
135:
131:
129:
125:
121:
119:
115:
100:
98:
97:Automorphisms
94:
90:
88:
84:
80:
78:
74:
70:
68:
64:
60:
58:
54:
50:
48:
44:
41:
38:
34:
30:
25:
20:
1113:
1109:
1088:
1076:
1068:
1063:
1045:
1039:
1033:
1017:
1013:
1010:Mislow, Kurt
1004:
995:
991:
985:
952:
948:
939:
914:
910:
904:
893:
879:
809:
799:
789:
785:queue number
755:
751:partial cube
734:
712:
706:
703:Applications
690:
541:
534:
524:
514:
504:
494:
460:
456:
444:
440:
433:
426:
415:
411:
407:
404:
392:
377:
363:
352:
344:
336:LCF notation
316:
265:
255:
239:
235:partial cube
210:
207:graph theory
203:mathematical
200:
158:Queue number
1108:vertices",
805:regular map
802:Petrie dual
531:Nauru graph
332:Hamiltonian
219:cubic graph
179:Hamiltonian
36:Named after
1143:Categories
945:Frucht, R.
871:References
811:Erv Wilson
463:) = (4, 1)
443:≡ ±1 (mod
384:isomorphic
311:It is the
300:It is the
279:Levi graph
277:It is the
260:It is the
231:non-planar
167:Properties
1130:0046-5755
977:122686848
895:MathWorld
779:. It has
709:chemistry
600:−
578:−
563:−
205:field of
187:Symmetric
183:Bipartite
790:All the
772:and a 3-
697:spectrum
529:and the
369:cycles.)
338:: . As
223:vertices
221:with 20
77:Diameter
47:Vertices
957:Bibcode
931:2371806
820:Gallery
745:in the
742:A110507
537:(12, 5)
527:(10, 2)
487:(24, 5)
483:(12, 5)
479:(10, 3)
475:(10, 2)
449:and is
304:of the
281:of the
272:decagon
201:In the
1128:
998:: 1205
975:
929:
783:3 and
721:ligand
695:: its
519:, the
517:(8, 3)
509:, the
507:(5, 2)
499:, the
497:(4, 1)
471:(8, 3)
467:(5, 2)
438:or if
347:> 0
268:(10,3)
233:cubic
209:, the
67:Radius
1116:(3),
1101:with
973:S2CID
927:JSTOR
792:cubic
766:girth
719:of 5-
340:Erdős
213:is a
171:Cubic
138:Genus
101:240 (
87:Girth
57:Edges
1126:ISSN
861:The
845:The
747:OEIS
542:The
431:and
429:= 10
361:and
355:+ 1)
1118:doi
1099:,3}
1050:doi
1046:263
1022:doi
965:doi
919:doi
787:2.
760:2,
707:In
436:= 2
420:is
366:+ 1
320:5,2
107:Ă— S
1145::
1124:,
1114:43
1112:,
1044:,
1016:,
996:11
994:,
971:,
963:,
953:70
951:,
925:,
915:69
913:,
892:,
888:,
753:.
539:.
485:,
481:,
477:,
473:,
469:,
465:,
459:,
414:,
351:(2
217:,
61:30
51:20
1120::
1105:p
1103:2
1097:p
1095:{
1052::
1024::
1018:3
980:.
967::
959::
934:.
921::
675:.
672:)
669:3
666:+
663:x
660:(
655:4
651:)
647:2
644:+
641:x
638:(
633:5
629:)
625:1
622:+
619:x
616:(
611:5
607:)
603:1
597:x
594:(
589:4
585:)
581:2
575:x
572:(
569:)
566:3
560:x
557:(
535:G
525:G
515:G
505:G
495:G
461:k
457:n
455:(
447:)
445:n
441:k
434:k
427:n
418:)
416:k
412:n
410:(
408:G
364:k
359:k
353:k
345:k
317:H
266:G
162:2
152:3
142:2
132:3
122:2
112:)
109:2
105:5
103:S
91:6
81:5
71:5
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
