411:
43:
55:
430:
of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged.
516:-vertex cubic graph has at most 2 (approximately 1.260) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best proven estimate for the number of distinct Hamiltonian cycles is
659:
conjectured that every cubic bridgeless graph has an exponential number of perfect matchings. The conjecture was recently proved, showing that every cubic bridgeless graph with
780:
552:
92:
591:
1324:
Xiao, Mingyu; Nagamochi, Hiroshi (2012), "An Exact
Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure",
1281:
Xiao, Mingyu; Nagamochi, Hiroshi (2013), "An Exact
Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure",
483:, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian,
467:, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the
1003:
Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic
Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
1083:
1476:
596:
399:
in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are also formed as the graphs of
1379:
303:
is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.
1308:
707:
319:
1527:
1139:
1410:
1015:
886:
873:, EUT report, vol. 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
868:
1160:
731:
292:
944:
816:
314:. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three
939:
759:
637:
in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.
386:
111:
743:
688:
382:
162:
994:
Bondy, J. A. and Murty, U. S. R. Graph Theory with
Applications. New York: North Holland, p. 240, 1976.
476:
174:
519:
480:
59:
1568:
1563:
1236:
719:
699:
684:
194:
1013:
Ellingham, M. N.; Horton, J. D. (1983), "Non-Hamiltonian 3-connected cubic bipartite graphs",
644:
640:
206:
119:
115:
64:
652:
254:
is one of the five smallest cubic graphs without any symmetries: it possesses only a single
1454:
1343:
1121:
917:
460:
456:
404:
326:
232:
8:
1480:
1158:
Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms",
942:(1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable",
703:
676:
452:
307:
20:
1458:
1347:
1444:
1377:
Alimonti, Paola; Kann, Viggo (2000), "Some APX-completeness results for cubic graphs",
1359:
1333:
1286:
1285:, Lecture Notes in Computer Science, vol. 7876, Springer-Verlag, pp. 96–107,
1263:
1245:
1212:
1092:
1075:
961:
921:
838:
797:
680:
656:
576:
444:
267:
255:
1393:
498:-vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the
422:
on a two-dimensional surface may be represented as a cubic graph structure known as a
1542:
1508:
1489:
1304:
1216:
1135:
1029:
925:
905:
842:
630:
440:
423:
346:
334:
801:
338:
1419:
1388:
1363:
1351:
1296:
1267:
1255:
1231:
1202:
1193:
1169:
1127:
1102:
1053:
1044:
Robinson, R.W.; Wormald, N.C. (1994), "Almost all regular graphs are
Hamiltonian",
1024:
953:
895:
828:
789:
672:
648:
448:
395:
315:
1492:
1234:; Norine, Serguei (2011), "Exponentially many perfect matchings in cubic graphs",
1300:
1120:
Gebauer, H. (2008), "On the number of
Hamilton cycles in bounded degree graphs",
913:
711:
427:
419:
281:
240:
221:
can be mapped to each other by exactly one symmetry of the graph. He showed that
182:
154:
138:
28:
1511:
793:
1424:
1071:
723:
634:
509:
472:
350:
330:
271:
166:
47:
24:
1355:
1259:
1173:
1131:
1557:
1546:
909:
735:
354:
311:
284:
with at most three colors. Therefore, every connected cubic graph other than
244:
190:
170:
158:
123:
36:
1057:
900:
833:
715:
491:
484:
468:
342:
251:
202:
178:
161:. Many well-known individual graphs are cubic and symmetric, including the
150:
103:
1123:
Proc. 4th
Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08)
325:
The bridgeless cubic graphs that do not have a Tait coloring are known as
225:
is at most 5, and provided examples of graphs with each possible value of
884:
Frucht, R. (1949), "Graphs of degree three with a given abstract group",
867:
Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976),
727:
619:
464:
210:
186:
99:
614:/6. The best known lower bound on the pathwidth of cubic graphs is 0.082
1207:
1106:
965:
561:
502:-vertex cubic graphs that are Hamiltonian tends to one in the limit as
400:
390:
236:
198:
32:
1097:
691:
in cubic graphs can be solved in time O(1.2312) and polynomial space.
1516:
1497:
778:
Foster, R. M. (1932), "Geometrical
Circuits of Electrical Networks",
603:
570:
213:
classified the symmetric cubic graphs by the smallest integer number
1188:
957:
410:
366:
1449:
1408:
Hliněný, Petr (2006), "Crossing number is hard for cubic graphs",
1338:
1291:
1250:
846:
1189:"Die Theorie der regulären Graphs (The theory of regular graphs)"
866:
747:
739:
675:
algorithms restricted to cubic graphs. For instance, by applying
374:
54:
42:
1526:
Brinkmann, Gunnar; Goedgebeur, Jan; Van
Cleemput, Nico (2013).
1525:
426:. In this structure, each vertex of a cubic graph represents a
781:
Transactions of the
American Institute of Electrical Engineers
414:
Representation of a planar embedding as a graph-encoded map
310:
every cubic graph needs either three or four colors for an
750:
to approximate to within any factor less than 1153/1152.
695:
407:
with the property that three faces meet at every vertex.
1487:
683:
of the graph, Fomin and Høie showed how to find their
618:. It is not known how to reduce this gap between this
1441:
Approximation Hardness of Graphic TSP on Cubic Graphs
1229:
579:
522:
369:
in several ways. For example, the cubic graphs with
67:
1506:
1230:
Esperet, Louis; Kardoš, František; King, Andrew D.;
979:Bonnington, C. Paul; Little, Charles H. C. (1995),
671:Several researchers have studied the complexity of
714:. These include the problems of finding a minimum
694:Several important graph optimization problems are
585:
546:
373:vertices describe the different ways of cutting a
357:. There is an infinite number of distinct snarks.
86:
1076:"The traveling salesman problem for cubic graphs"
1555:
1438:
1283:Theory and Applications of Models of Computation
978:
734:(the minimum number of edges which cross in any
261:
1528:"The history of the generation of cubic graphs"
1043:
1012:
563:
239:(the smallest semi-symmetric cubic graph), the
742:for cubic graphs but may be approximated. The
1323:
1280:
1477:"Cubic symmetric graphs (The Foster Census)"
1376:
1084:Journal of Graph Algorithms and Applications
710:whose approximation ratio tends to 1 unless
666:
217:such that each two oriented paths of length
122:three. In other words, a cubic graph is a 3-
1439:Karpinski, Marek; Schmied, Richard (2013),
981:The Foundations of Topological Graph Theory
706:is bounded by a constant, they do not have
663:vertices has at least 2 perfect matchings.
403:in three dimensions, polyhedra such as the
270:every connected cubic graph other than the
1401:
475:constructed two more counterexamples: the
1448:
1423:
1392:
1337:
1290:
1274:
1249:
1206:
1187:Petersen, Julius Peter Christian (1891),
1157:
1096:
1028:
899:
832:
771:
322:every bicubic graph has a Tait coloring.
1186:
1070:
409:
360:
53:
41:
1407:
1223:
1180:
1153:
1151:
1119:
597:(more unsolved problems in mathematics)
487:allows it to be represented concisely.
1556:
938:
883:
870:Computer investigation of cubic graphs
777:
746:on cubic graphs has been proven to be
1507:
1488:
814:
708:polynomial time approximation schemes
1148:
1006:
997:
988:
698:, meaning that, although they have
557:
153:began collecting examples of cubic
16:Graph with all vertices of degree 3
13:
14:
1580:
1474:
1468:
817:"On the symmetry of cubic graphs"
1046:Random Structures and Algorithms
439:There has been much research on
434:
365:Cubic graphs arise naturally in
94:is an example of a bicubic graph
1432:
1411:Journal of Combinatorial Theory
1370:
1317:
1113:
1064:
1037:
1016:Journal of Combinatorial Theory
887:Canadian Journal of Mathematics
610:-vertex cubic graph is at most
564:Unsolved problem in mathematics
126:. Cubic graphs are also called
1161:Information Processing Letters
972:
932:
877:
860:
808:
547:{\displaystyle O({1.276}^{n})}
541:
526:
459:provided a counter-example to
1:
1394:10.1016/S0304-3975(98)00158-3
945:American Mathematical Monthly
765:
569:What is the largest possible
447:conjectured that every cubic
320:KĹ‘nig's line coloring theorem
262:Coloring and independent sets
258:, the identity automorphism.
1541:(2–3). Nova Science: 67–89.
1380:Theoretical Computer Science
1301:10.1007/978-3-642-38236-9_10
1030:10.1016/0095-8956(83)90046-1
760:Table of simple cubic graphs
7:
794:10.1109/T-AIEE.1932.5056068
753:
744:Travelling Salesman Problem
738:) of a cubic graph is also
689:travelling salesman problem
490:If a cubic graph is chosen
157:, forming the start of the
144:
10:
1585:
1425:10.1016/j.jctb.2005.09.009
443:of cubic graphs. In 1880,
18:
1356:10.1007/s00453-015-9970-4
1260:10.1016/j.aim.2011.03.015
1174:10.1016/j.ipl.2005.10.012
1132:10.1137/1.9781611972986.8
667:Algorithms and complexity
235:cubic graphs include the
700:approximation algorithms
685:maximum independent sets
643:states that every cubic
60:complete bipartite graph
19:Not to be confused with
1237:Advances in Mathematics
720:maximum independent set
512:conjectured that every
477:Ellingham–Horton graphs
87:{\displaystyle K_{3,3}}
1535:Int. J. Chem. Modeling
1058:10.1002/rsa.3240050209
901:10.4153/CJM-1949-033-6
834:10.4153/CJM-1959-057-2
587:
548:
415:
389:to be a 1-dimensional
95:
88:
51:
815:Tutte, W. T. (1959),
588:
549:
481:Barnette's conjecture
413:
385:. If one considers a
361:Topology and geometry
89:
57:
45:
1126:, pp. 241–248,
629:It follows from the
593:-vertex cubic graph?
577:
520:
457:William Thomas Tutte
405:regular dodecahedron
65:
1459:2013arXiv1304.6800K
1348:2012arXiv1212.6831X
704:approximation ratio
677:dynamic programming
492:uniformly at random
453:Hamiltonian circuit
393:, cubic graphs are
329:. They include the
299:/3 vertices, where
195:Tutte–Coxeter graph
175:Möbius–Kantor graph
1509:Weisstein, Eric W.
1490:Weisstein, Eric W.
1208:10.1007/BF02392606
1107:10.7155/jgaa.00137
681:path decomposition
641:Petersen's theorem
583:
544:
506:goes to infinity.
416:
256:graph automorphism
96:
84:
52:
1310:978-3-642-38236-9
983:, Springer-Verlag
631:handshaking lemma
586:{\displaystyle n}
461:Tait's conjecture
424:graph-encoded map
347:double-star snark
316:perfect matchings
207:Biggs–Smith graph
50:is a cubic graph.
1576:
1550:
1532:
1522:
1521:
1503:
1502:
1484:
1479:. Archived from
1463:
1461:
1452:
1436:
1430:
1428:
1427:
1405:
1399:
1397:
1396:
1387:(1–2): 123–134,
1374:
1368:
1366:
1341:
1321:
1315:
1313:
1294:
1278:
1272:
1270:
1253:
1244:(4): 1646–1664,
1227:
1221:
1219:
1210:
1194:Acta Mathematica
1184:
1178:
1176:
1155:
1146:
1144:
1117:
1111:
1109:
1100:
1080:
1068:
1062:
1060:
1041:
1035:
1033:
1032:
1010:
1004:
1001:
995:
992:
986:
984:
976:
970:
968:
936:
930:
928:
903:
881:
875:
874:
864:
858:
856:
855:
854:
845:, archived from
836:
812:
806:
804:
775:
673:exponential time
649:perfect matching
626:/6 upper bound.
592:
590:
589:
584:
565:
558:Other properties
553:
551:
550:
545:
540:
539:
534:
463:, the 46-vertex
449:polyhedral graph
401:simple polyhedra
308:Vizing's theorem
155:symmetric graphs
151:Ronald M. Foster
128:trivalent graphs
93:
91:
90:
85:
83:
82:
1584:
1583:
1579:
1578:
1577:
1575:
1574:
1573:
1554:
1553:
1530:
1493:"Bicubic Graph"
1475:Royle, Gordon.
1471:
1466:
1437:
1433:
1406:
1402:
1375:
1371:
1322:
1318:
1311:
1279:
1275:
1228:
1224:
1201:(15): 193–220,
1185:
1181:
1156:
1149:
1142:
1118:
1114:
1078:
1072:Eppstein, David
1069:
1065:
1042:
1038:
1011:
1007:
1002:
998:
993:
989:
977:
973:
958:10.2307/2319844
937:
933:
882:
878:
865:
861:
852:
850:
813:
809:
776:
772:
768:
756:
732:crossing number
687:in time 2. The
669:
600:
599:
594:
578:
575:
574:
567:
560:
535:
530:
529:
521:
518:
517:
437:
420:graph embedding
363:
293:independent set
290:
282:vertex coloring
279:
268:Brooks' theorem
264:
241:Ljubljana graph
183:Desargues graph
147:
139:bipartite graph
72:
68:
66:
63:
62:
40:
29:hypercube graph
25:cubic functions
17:
12:
11:
5:
1582:
1572:
1571:
1569:Regular graphs
1566:
1564:Graph families
1552:
1551:
1523:
1504:
1485:
1483:on 2011-10-23.
1470:
1469:External links
1467:
1465:
1464:
1431:
1418:(4): 455–471,
1400:
1369:
1332:(2): 713–741,
1316:
1309:
1273:
1222:
1179:
1168:(5): 191–196,
1147:
1140:
1112:
1063:
1052:(2): 363–374,
1036:
1023:(3): 350–353,
1005:
996:
987:
971:
952:(3): 221–239,
931:
894:(4): 365–378,
876:
859:
807:
788:(2): 309–317,
769:
767:
764:
763:
762:
755:
752:
724:dominating set
668:
665:
635:Leonhard Euler
595:
582:
568:
562:
559:
556:
543:
538:
533:
528:
525:
510:David Eppstein
473:Mark Ellingham
436:
433:
383:pairs of pants
362:
359:
351:Szekeres snark
339:Blanuša snarks
335:Tietze's graph
331:Petersen graph
288:
277:
272:complete graph
263:
260:
233:Semi-symmetric
167:Petersen graph
146:
143:
81:
78:
75:
71:
48:Petersen graph
15:
9:
6:
4:
3:
2:
1581:
1570:
1567:
1565:
1562:
1561:
1559:
1548:
1544:
1540:
1536:
1529:
1524:
1519:
1518:
1513:
1512:"Cubic Graph"
1510:
1505:
1500:
1499:
1494:
1491:
1486:
1482:
1478:
1473:
1472:
1460:
1456:
1451:
1446:
1442:
1435:
1426:
1421:
1417:
1413:
1412:
1404:
1395:
1390:
1386:
1382:
1381:
1373:
1365:
1361:
1357:
1353:
1349:
1345:
1340:
1335:
1331:
1327:
1320:
1312:
1306:
1302:
1298:
1293:
1288:
1284:
1277:
1269:
1265:
1261:
1257:
1252:
1247:
1243:
1239:
1238:
1233:
1226:
1218:
1214:
1209:
1204:
1200:
1196:
1195:
1190:
1183:
1175:
1171:
1167:
1163:
1162:
1154:
1152:
1143:
1141:9781611972986
1137:
1133:
1129:
1125:
1124:
1116:
1108:
1104:
1099:
1098:cs.DS/0302030
1094:
1090:
1086:
1085:
1077:
1073:
1067:
1059:
1055:
1051:
1047:
1040:
1031:
1026:
1022:
1018:
1017:
1009:
1000:
991:
982:
975:
967:
963:
959:
955:
951:
947:
946:
941:
935:
927:
923:
919:
915:
911:
907:
902:
897:
893:
889:
888:
880:
872:
871:
863:
849:on 2011-07-16
848:
844:
840:
835:
830:
826:
822:
821:Can. J. Math.
818:
811:
803:
799:
795:
791:
787:
783:
782:
774:
770:
761:
758:
757:
751:
749:
745:
741:
737:
736:graph drawing
733:
729:
725:
721:
717:
713:
709:
705:
701:
697:
692:
690:
686:
682:
678:
674:
664:
662:
658:
654:
650:
646:
642:
638:
636:
632:
627:
625:
621:
617:
613:
609:
605:
598:
580:
572:
555:
536:
531:
523:
515:
511:
507:
505:
501:
497:
493:
488:
486:
482:
478:
474:
470:
466:
462:
458:
454:
450:
446:
442:
441:Hamiltonicity
435:Hamiltonicity
432:
429:
425:
421:
418:An arbitrary
412:
408:
406:
402:
398:
397:
392:
388:
384:
380:
376:
372:
368:
358:
356:
355:Watkins snark
352:
348:
344:
340:
336:
332:
328:
323:
321:
317:
313:
312:edge coloring
309:
306:According to
304:
302:
298:
294:
287:
283:
276:
273:
269:
266:According to
259:
257:
253:
248:
246:
245:Tutte 12-cage
242:
238:
234:
230:
229:from 1 to 5.
228:
224:
220:
216:
212:
208:
204:
200:
196:
192:
191:Coxeter graph
188:
184:
180:
176:
172:
171:Heawood graph
168:
164:
163:utility graph
160:
159:Foster census
156:
152:
142:
140:
136:
135:bicubic graph
131:
129:
125:
124:regular graph
121:
117:
114:in which all
113:
109:
105:
101:
79:
76:
73:
69:
61:
56:
49:
44:
38:
37:cubical graph
34:
30:
26:
22:
1538:
1534:
1515:
1496:
1481:the original
1440:
1434:
1415:
1414:, Series B,
1409:
1403:
1384:
1378:
1372:
1329:
1326:Algorithmica
1325:
1319:
1282:
1276:
1241:
1235:
1232:Kráľ, Daniel
1225:
1198:
1192:
1182:
1165:
1159:
1122:
1115:
1091:(1): 61–81,
1088:
1082:
1066:
1049:
1045:
1039:
1020:
1019:, Series B,
1014:
1008:
999:
990:
980:
974:
949:
943:
934:
891:
885:
879:
869:
862:
851:, retrieved
847:the original
824:
820:
810:
785:
779:
773:
716:vertex cover
693:
670:
660:
647:graph has a
639:
633:, proven by
628:
623:
615:
611:
607:
601:
513:
508:
503:
499:
495:
489:
485:LCF notation
469:Horton graph
438:
417:
394:
378:
370:
364:
343:flower snark
324:
305:
300:
296:
295:of at least
285:
274:
265:
252:Frucht graph
249:
231:
226:
222:
218:
214:
203:Foster graph
179:Pappus graph
148:
134:
132:
127:
107:
104:graph theory
100:mathematical
97:
827:: 621–624,
728:maximum cut
620:lower bound
465:Tutte graph
211:W. T. Tutte
187:Nauru graph
137:is a cubic
108:cubic graph
1558:Categories
940:Isaacs, R.
853:2010-07-21
766:References
722:, minimum
645:bridgeless
494:among all
391:CW complex
243:, and the
237:Gray graph
199:Dyck graph
33:cube graph
1547:1941-3955
1517:MathWorld
1498:MathWorld
1450:1304.6800
1339:1212.6831
1292:1212.6831
1251:1012.2878
1217:123779343
926:124723321
910:0008-414X
843:124273238
604:pathwidth
571:pathwidth
471:. Later,
445:P.G. Tait
377:of genus
149:In 1932,
102:field of
1074:(2007),
802:51638449
754:See also
696:APX hard
622:and the
367:topology
353:and the
205:and the
145:Symmetry
116:vertices
1455:Bibcode
1364:7654681
1344:Bibcode
1268:4401537
966:2319844
918:0032987
748:NP-hard
740:NP-hard
657:Plummer
606:of any
396:generic
375:surface
291:has an
98:In the
1545:
1362:
1307:
1266:
1215:
1138:
964:
924:
916:
908:
841:
800:
730:. The
726:, and
702:whose
653:Lovász
573:of an
451:has a
349:, the
345:, the
341:, the
337:, the
327:snarks
280:has a
201:, the
197:, the
193:, the
189:, the
185:, the
181:, the
177:, the
173:, the
169:, the
165:, the
120:degree
21:graphs
1531:(PDF)
1445:arXiv
1360:S2CID
1334:arXiv
1287:arXiv
1264:S2CID
1246:arXiv
1213:S2CID
1093:arXiv
1079:(PDF)
962:JSTOR
922:S2CID
839:S2CID
798:S2CID
679:to a
532:1.276
387:graph
381:into
379:g ≥ 2
318:. By
118:have
112:graph
110:is a
106:, a
1543:ISSN
1305:ISBN
1136:ISBN
906:ISSN
712:P=NP
655:and
602:The
428:flag
371:2g-2
250:The
58:The
46:The
1420:doi
1389:doi
1385:237
1352:doi
1297:doi
1256:doi
1242:227
1203:doi
1170:doi
1128:doi
1103:doi
1054:doi
1025:doi
954:doi
896:doi
829:doi
790:doi
455:.
23:of
1560::
1537:.
1533:.
1514:.
1495:.
1453:,
1443:,
1416:96
1383:,
1358:,
1350:,
1342:,
1330:74
1328:,
1303:,
1295:,
1262:,
1254:,
1240:,
1211:,
1199:15
1197:,
1191:,
1166:97
1164:,
1150:^
1134:,
1101:,
1089:11
1087:,
1081:,
1048:,
1021:34
960:,
950:82
948:,
920:,
914:MR
912:,
904:,
890:,
837:,
825:11
823:,
819:,
796:,
786:51
784:,
718:,
651:.
554:.
479:.
333:,
247:.
209:.
141:.
133:A
130:.
35:,
31:,
27:,
1549:.
1539:5
1520:.
1501:.
1462:.
1457::
1447::
1429:.
1422::
1398:.
1391::
1367:.
1354::
1346::
1336::
1314:.
1299::
1289::
1271:.
1258::
1248::
1220:.
1205::
1177:.
1172::
1145:.
1130::
1110:.
1105::
1095::
1061:.
1056::
1050:5
1034:.
1027::
985:.
969:.
956::
929:.
898::
892:1
857:.
831::
805:.
792::
661:n
624:n
616:n
612:n
608:n
581:n
566::
542:)
537:n
527:(
524:O
514:n
504:n
500:n
496:n
301:n
297:n
289:4
286:K
278:4
275:K
227:s
223:s
219:s
215:s
80:3
77:,
74:3
70:K
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
