31:
570:, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.
752:, and in 1988 (when Foster was 92) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form. The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices (ten of these are also
577:
is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.
166:
705:- they are complete graphs with a set of edges making a perfect matching removed. Additional families of symmetric graphs with an even number of vertices 2n, are the evenly split
697:. Extension of the cube to n dimensions gives the hypercube graphs (with 2 vertices and degree n). Similarly extension of the octahedron to n dimensions gives the graphs of the
1405:
273:
221:
1469:. Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
1421:"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988)
740:(i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. They all have an even number of vertices. The
599:
vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A
364:
1466:
562:
degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called
1426:
1339:
1249:
1204:
290:
of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called
1159:
350:
are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example,
1492:
554:
symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of
673:. Further symmetric graphs are formed by the vertices and edges of the regular and quasiregular polyhedra: the
1141: ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for
17:
283:
121:
59:
1100:
551:
1164:
999:
915:
1271:
753:
574:
371:
226:
177:
829:
706:
1502:
1497:
1472:
1357:
1111:
1060:
768:
491:
327:
1389:
1154:
387:
379:
1241:
1088:
1080:
563:
469:
453:
331:
74:
1233:
701:, this family of graphs (with 2n vertices and degree 2n-2) are sometimes referred to as the
1126:
775:
702:
559:
555:
535:
461:
429:
351:
8:
347:
1450:
1278:
728:
forms an example of a symmetric graph with infinitely many vertices and infinite degree
1302:
279:
113:
43:
653:
Note that conventionally the term "symmetric graph" is not complementary to the term "
330:. Since the definition above maps one edge to another, a symmetric graph must also be
1422:
1335:
1245:
1234:
1200:
694:
1366:
1310:
744:
and its extensions provide such lists. The Foster census was begun in the 1930s by
654:
542:
1355:
Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive".
975:
718:
567:
511:
323:
42:) symmetric graph. Any pair of adjacent vertices can be mapped to another by an
1476:
1384:
875:
803:
698:
670:
35:
1486:
1104:
1040:
895:
690:
657:," as the latter refers to a graph that has no nontrivial symmetries at all.
499:
355:
1370:
1315:
1297:
1229:
1225:
1084:
1076:
955:
935:
745:
686:
527:
287:
55:
665:
Two basic families of symmetric graphs for any number of vertices are the
1199:(2nd ed.). Cambridge: Cambridge University Press. pp. 118–140.
995:
737:
714:
682:
666:
51:
39:
1072:
1020:
725:
678:
1083:. The ten distance-transitive graphs listed above, together with the
749:
736:
Combining the symmetry condition with the restriction that graphs be
631:
are simply edges, every symmetric graph of degree 3 or more must be
589:
717:
on 2n vertices. Many other symmetric graphs can be classified as
609:
is a graph such that the automorphism group acts transitively on
334:. However, an edge-transitive graph need not be symmetric, since
30:
27:
Graph in which all ordered pairs of linked nodes are automorphic
646:
can be used to further classify symmetric graphs. The cube is
1406:
Transactions of the
American Institute of Electrical Engineers
1403:
Foster, R. M. "Geometrical
Circuits of Electrical Networks."
855:
674:
1473:
Trivalent (cubic) symmetric graphs on up to 10000 vertices
1114:
in general, the vertex-connectivity is bounded below by 2(
1394:
J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
1298:"Vertex and Edge Transitive, But Not 1-Transitive Graphs"
46:, since any five-vertex ring can be mapped to any other.
1329:
229:
180:
124:
1272:"Automorphism groups, isomorphism, reconstruction"
566:. The smallest connected half-transitive graph is
267:
215:
160:
1091:, are the only cubic distance-transitive graphs.
1484:
1390:Trivalent symmetric graphs on up to 768 vertices
1137:-transitive graphs of degree 3 or more for
1133: – 1). However, there are no finite
1071:Other well known cubic symmetric graphs are the
1194:
365:Graph families defined by their automorphisms
1103:of a symmetric graph is always equal to the
278:In other words, a graph is symmetric if its
1224:
1467:Cubic symmetric graphs (The Foster Census)
1125:-transitive graph of degree 3 or more has
1314:
731:
1220:
1218:
1216:
29:
1445:
1443:
1323:
1265:
1263:
1261:
1190:
1188:
1186:
1184:
1182:
1180:
14:
1485:
1295:
1065:distance-transitive, 5-arc-transitive
1045:distance-transitive, 3-arc-transitive
980:distance-transitive, 3-arc-transitive
960:distance-transitive, 2-arc-transitive
940:distance-transitive, 3-arc-transitive
900:distance-transitive, 4-arc-transitive
880:distance-transitive, 3-arc-transitive
860:distance-transitive, 2-arc-transitive
840:distance-transitive, 3-arc-transitive
814:distance-transitive, 2-arc-transitive
161:{\displaystyle f:V(G)\rightarrow V(G)}
73:) if, given any two pairs of adjacent
1330:Gross, J.L. & Yellen, J. (2004).
1269:
1213:
1440:
1354:
1258:
1177:
756:; the exceptions are as indicated):
24:
25:
1514:
1460:
360:
1431:
268:{\displaystyle f(v_{1})=v_{2}.}
1415:
1397:
1378:
1348:
1289:
1240:. New York: Springer. p.
954:The vertices and edges of the
854:The vertices and edges of the
358:, but not vertex-transitive.
246:
233:
216:{\displaystyle f(u_{1})=u_{2}}
197:
184:
155:
149:
143:
140:
134:
13:
1:
1170:
1094:
322:), a symmetric graph without
7:
1148:
660:
462:edge-transitive and regular
454:vertex- and edge-transitive
10:
1519:
1453:", from Wolfram MathWorld.
1334:. CRC Press. p. 491.
1000:generalized Petersen graph
404:symmetric (arc-transitive)
1283:Handbook of Combinatorics
748:while he was employed by
707:complete bipartite graphs
575:distance-transitive graph
363:
1332:Handbook of Graph Theory
1112:vertex-transitive graphs
830:complete bipartite graph
354:are edge-transitive and
304:By definition (ignoring
1358:Journal of Graph Theory
1160:Gallery of named graphs
1089:Biggs–Smith graph
1081:Biggs–Smith graph
1493:Algebraic graph theory
1412:, 309–317, 1932.
1371:10.1002/jgt.3190050210
1316:10.4153/CMB-1970-047-8
1236:Algebraic Graph Theory
1197:Algebraic Graph Theory
1195:Biggs, Norman (1993).
1155:Algebraic graph theory
732:Cubic symmetric graphs
669:(of degree 2) and the
558:degree. However, for
269:
217:
162:
47:
1451:Cubic Symmetric Graph
1449:Weisstein, Eric W., "
703:cocktail party graphs
352:semi-symmetric graphs
270:
218:
163:
33:
1281:; Lovász, L (eds.).
1118: + 1)/3.
227:
178:
122:
1296:Bouwer, Z. (1970).
1110:. In contrast, for
1101:vertex-connectivity
1061:Tutte–Coxeter graph
916:Möbius–Kantor graph
754:distance-transitive
642:, and the value of
588:is defined to be a
508:(if bipartite)
450:(if connected)
372:distance-transitive
1303:Canad. Math. Bull.
280:automorphism group
265:
213:
158:
48:
1270:Babai, L (1996).
1069:
1068:
1025:1-arc-transitive
1005:2-arc-transitive
920:2-arc-transitive
695:icosidodecahedron
548:
547:
492:vertex-transitive
328:vertex-transitive
324:isolated vertices
16:(Redirected from
1510:
1454:
1447:
1438:
1435:
1429:
1419:
1413:
1401:
1395:
1382:
1376:
1374:
1352:
1346:
1345:
1327:
1321:
1320:
1318:
1293:
1287:
1286:
1277:. In Graham, R;
1276:
1267:
1256:
1255:
1239:
1222:
1211:
1210:
1192:
1145: ≥ 6.
759:
758:
746:Ronald M. Foster
719:circulant graphs
655:asymmetric graph
649:
645:
641:
637:
635:
630:
626:
624:
622:
615:
613:
606:
604:
598:
587:
585:
423:
417:
388:strongly regular
380:distance-regular
361:
345:
341:
337:
321:
312:
294:
274:
272:
271:
266:
261:
260:
245:
244:
222:
220:
219:
214:
212:
211:
196:
195:
167:
165:
164:
159:
111:
107:
91:
64:
21:
1518:
1517:
1513:
1512:
1511:
1509:
1508:
1507:
1483:
1482:
1463:
1458:
1457:
1448:
1441:
1436:
1432:
1420:
1416:
1402:
1398:
1383:
1379:
1353:
1349:
1342:
1328:
1324:
1294:
1290:
1274:
1268:
1259:
1252:
1223:
1214:
1207:
1193:
1178:
1173:
1151:
1097:
976:Desargues graph
837:
811:
734:
721:(but not all).
712:
699:cross-polytopes
671:complete graphs
663:
650:, for example.
647:
643:
639:
633:
632:
628:
620:
619:
617:
611:
610:
602:
601:
593:
583:
582:
564:half-transitive
510:
509:
470:edge-transitive
452:
451:
418:
412:
343:
339:
335:
332:edge-transitive
320:
314:
311:
305:
299:flag-transitive
292:
256:
252:
240:
236:
228:
225:
224:
207:
203:
191:
187:
179:
176:
175:
123:
120:
119:
109:
106:
99:
93:
90:
83:
77:
62:
28:
23:
22:
15:
12:
11:
5:
1516:
1506:
1505:
1503:Regular graphs
1500:
1498:Graph families
1495:
1481:
1480:
1477:Marston Conder
1470:
1462:
1461:External links
1459:
1456:
1455:
1439:
1430:
1414:
1396:
1385:Marston Conder
1377:
1365:(2): 201–204.
1347:
1340:
1322:
1288:
1257:
1250:
1212:
1205:
1175:
1174:
1172:
1169:
1168:
1167:
1162:
1157:
1150:
1147:
1096:
1093:
1067:
1066:
1063:
1057:
1054:
1051:
1047:
1046:
1043:
1037:
1034:
1031:
1027:
1026:
1023:
1017:
1014:
1011:
1007:
1006:
1003:
992:
989:
986:
982:
981:
978:
972:
969:
966:
962:
961:
958:
952:
949:
946:
942:
941:
938:
932:
929:
926:
922:
921:
918:
912:
909:
906:
902:
901:
898:
892:
889:
886:
882:
881:
878:
876:Petersen graph
872:
869:
866:
862:
861:
858:
852:
849:
846:
842:
841:
838:
835:
826:
823:
820:
816:
815:
812:
809:
804:complete graph
800:
797:
794:
790:
789:
784:
779:
772:
765:
733:
730:
710:
662:
659:
546:
545:
540:
538:
536:zero-symmetric
533:
530:
524:
523:
521:
519:
515:
514:
507:
505:
502:
497:
494:
488:
487:
484:
482:
479:
477:
473:
472:
467:
464:
459:
456:
449:
446:
445:
443:
441:
439:
437:
433:
432:
430:skew-symmetric
427:
425:
422: ≥ 2
409:
406:
400:
399:
397:
395:
391:
390:
385:
382:
377:
374:
368:
367:
318:
309:
276:
275:
264:
259:
255:
251:
248:
243:
239:
235:
232:
210:
206:
202:
199:
194:
190:
186:
183:
169:
168:
157:
154:
151:
148:
145:
142:
139:
136:
133:
130:
127:
112:, there is an
104:
97:
88:
81:
71:arc-transitive
36:Petersen graph
26:
9:
6:
4:
3:
2:
1515:
1504:
1501:
1499:
1496:
1494:
1491:
1490:
1488:
1478:
1474:
1471:
1468:
1465:
1464:
1452:
1446:
1444:
1437:Biggs, p. 148
1434:
1428:
1427:0-919611-19-2
1424:
1418:
1411:
1408:
1407:
1400:
1393:
1391:
1386:
1381:
1372:
1368:
1364:
1360:
1359:
1351:
1343:
1341:1-58488-090-2
1337:
1333:
1326:
1317:
1312:
1308:
1305:
1304:
1299:
1292:
1284:
1280:
1273:
1266:
1264:
1262:
1253:
1251:0-387-95220-9
1247:
1243:
1238:
1237:
1231:
1230:Royle, Gordon
1227:
1226:Godsil, Chris
1221:
1219:
1217:
1208:
1206:0-521-45897-8
1202:
1198:
1191:
1189:
1187:
1185:
1183:
1181:
1176:
1166:
1163:
1161:
1158:
1156:
1153:
1152:
1146:
1144:
1140:
1136:
1132:
1128:
1124:
1119:
1117:
1113:
1109:
1106:
1102:
1092:
1090:
1086:
1082:
1078:
1074:
1064:
1062:
1058:
1055:
1052:
1049:
1048:
1044:
1042:
1041:Coxeter graph
1038:
1035:
1032:
1029:
1028:
1024:
1022:
1018:
1015:
1012:
1009:
1008:
1004:
1001:
997:
993:
990:
987:
984:
983:
979:
977:
973:
970:
967:
964:
963:
959:
957:
953:
950:
947:
944:
943:
939:
937:
933:
930:
927:
924:
923:
919:
917:
913:
910:
907:
904:
903:
899:
897:
896:Heawood graph
893:
890:
887:
884:
883:
879:
877:
873:
870:
867:
864:
863:
859:
857:
853:
850:
847:
844:
843:
839:
834:
831:
827:
824:
821:
818:
817:
813:
808:
805:
801:
798:
795:
792:
791:
788:
785:
783:
780:
778:
777:
773:
771:
770:
766:
764:
761:
760:
757:
755:
751:
747:
743:
742:Foster census
739:
729:
727:
722:
720:
716:
708:
704:
700:
696:
692:
691:cuboctahedron
688:
684:
680:
676:
672:
668:
658:
656:
651:
616:, but not on
608:
596:
591:
579:
576:
571:
569:
565:
561:
557:
553:
544:
541:
539:
537:
534:
531:
529:
526:
525:
522:
520:
517:
516:
513:
506:
503:
501:
498:
495:
493:
490:
489:
485:
483:
480:
478:
475:
474:
471:
468:
465:
463:
460:
457:
455:
448:
447:
444:
442:
440:
438:
435:
434:
431:
428:
426:
424:
421:
415:
410:
407:
405:
402:
401:
398:
396:
393:
392:
389:
386:
383:
381:
378:
375:
373:
370:
369:
366:
362:
359:
357:
353:
349:
342:, but not to
338:might map to
333:
329:
326:must also be
325:
317:
308:
302:
300:
296:
289:
288:ordered pairs
285:
281:
262:
257:
253:
249:
241:
237:
230:
208:
204:
200:
192:
188:
181:
174:
173:
172:
152:
146:
137:
131:
128:
125:
118:
117:
116:
115:
103:
96:
87:
80:
76:
72:
68:
61:
57:
53:
45:
41:
37:
32:
19:
18:Foster census
1433:
1417:
1409:
1404:
1399:
1388:
1380:
1362:
1356:
1350:
1331:
1325:
1306:
1301:
1291:
1282:
1279:Grötschel, M
1235:
1196:
1142:
1138:
1134:
1130:
1122:
1120:
1115:
1107:
1098:
1085:Foster graph
1077:Foster graph
1070:
956:dodecahedron
936:Pappus graph
832:
806:
786:
781:
774:
767:
762:
741:
735:
723:
715:crown graphs
687:dodecahedron
667:cycle graphs
664:
652:
648:2-transitive
600:
594:
580:
572:
568:Holt's graph
549:
528:Cayley graph
419:
416:-transitive,
413:
411:
403:
315:
306:
303:
298:
291:
284:transitively
277:
170:
114:automorphism
101:
94:
85:
78:
70:
66:
56:graph theory
52:mathematical
49:
44:automorphism
1309:: 231–237.
1285:. Elsevier.
1165:Regular map
1129:at least 2(
996:Nauru graph
683:icosahedron
636:-transitive
605:-transitive
348:Star graphs
295:-transitive
1487:Categories
1171:References
1095:Properties
1073:Dyck graph
1021:F26A graph
726:Rado graph
679:octahedron
543:asymmetric
171:such that
750:Bell Labs
638:for some
627:. Since
552:connected
512:biregular
144:→
67:symmetric
54:field of
1232:(2001).
1149:See also
1087:and the
1079:and the
1002:G(12,5))
769:Diameter
763:Vertices
713:and the
661:Examples
590:sequence
532:←
518:↑
504:→
496:→
486:↓
481:↓
476:↓
466:→
458:→
436:↓
408:←
394:↓
384:←
376:→
75:vertices
1479:, 2011.
500:regular
356:regular
50:In the
1425:
1338:
1248:
1203:
1105:degree
1075:, the
693:, and
629:1-arcs
625:)-arcs
550:Every
38:is a (
1275:(PDF)
1127:girth
998:(the
787:Notes
782:Graph
776:Girth
738:cubic
614:-arcs
607:graph
293:1-arc
282:acts
60:graph
40:cubic
1423:ISBN
1336:ISBN
1246:ISBN
1201:ISBN
1099:The
1059:The
1039:The
1019:The
994:The
974:The
934:The
914:The
894:The
874:The
856:cube
828:The
802:The
724:The
675:cube
586:-arc
560:even
313:and
223:and
92:and
69:(or
58:, a
34:The
1367:doi
1311:doi
836:3,3
711:n,n
623:+ 1
597:+ 1
592:of
556:odd
344:d—c
340:c—d
336:a—b
297:or
286:on
108:of
65:is
1489::
1475:.
1442:^
1410:51
1387:,
1361:.
1307:13
1300:.
1260:^
1244:.
1242:59
1228:;
1215:^
1179:^
1121:A
1050:30
1030:28
1010:26
985:24
965:20
945:20
925:18
905:16
885:14
865:10
689:,
685:,
681:,
677:,
581:A
573:A
346:.
301:.
1392:,
1375:.
1373:.
1369::
1363:5
1344:.
1319:.
1313::
1254:.
1209:.
1143:t
1139:t
1135:t
1131:t
1123:t
1116:d
1108:d
1056:8
1053:4
1036:7
1033:4
1016:6
1013:5
991:6
988:4
971:6
968:5
951:5
948:5
931:6
928:4
911:6
908:4
891:6
888:3
871:5
868:2
851:4
848:3
845:8
833:K
825:4
822:2
819:6
810:4
807:K
799:3
796:1
793:4
709:K
644:t
640:t
634:t
621:t
618:(
612:t
603:t
595:t
584:t
420:t
414:t
319:2
316:u
310:1
307:u
263:.
258:2
254:v
250:=
247:)
242:1
238:v
234:(
231:f
209:2
205:u
201:=
198:)
193:1
189:u
185:(
182:f
156:)
153:G
150:(
147:V
141:)
138:G
135:(
132:V
129::
126:f
110:G
105:2
102:v
100:—
98:2
95:u
89:1
86:v
84:—
82:1
79:u
63:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
