83:, which accounts for two edges per vertex. The third edge from each vertex can then be described by how many positions clockwise (positive) or counter-clockwise (negative) it leads. The basic form of the LCF notation is just the sequence of these numbers of positions, starting from an arbitrarily chosen vertex and written in square brackets. The numbers between the brackets are interpreted
20:
543:
A more complex extended version of LCF notation was provided by
Coxeter, Frucht, and Powers in later work. In particular, they introduced an "anti-palindromic" notation: if the second half of the numbers between the square brackets was the reverse of the first half, but with all the signs changed,
125:
LCF notation is useful in publishing concise descriptions of
Hamiltonian cubic graphs, such as the examples below. In addition, some software packages for manipulating graphs include utilities for creating a graph from its LCF notation.
117:, shown on the right, has four repetitions of the same six offsets, and can be represented by the LCF notation . A single graph may have multiple different LCF notations, depending on the choices of Hamiltonian cycle and starting vertex.
71:, and the LCF notation specifies how far along the cycle each vertex's third neighbor is. A single graph may have multiple different representations in LCF notation.
900:
733:
721:
544:
then it was replaced by a semicolon and a dash. The Nauru graph satisfies this condition with , and so can be written in the extended notation.
1069:
848:
1064:
893:
764:
669:
600:
994:
714:
113:
Often the pattern repeats, and the number of repetitions can be indicated by a superscript in the notation. For example, the
886:
746:
52:
168:
268:
921:
999:
392:
618:
453:
428:
102: − 1 do not appear in this sequence of numbers, because they would correspond either to a
489:
243:
68:
718:
1017:
657:
355:
293:
103:
854:
678:
584:
84:
567:
829:
760:
596:
580:
129:
If a graph is represented by LCF notation, it is straightforward to test whether the graph is
754:
588:
941:
936:
729:
688:
627:
64:
48:
774:
700:
639:
770:
725:
696:
653:
635:
513:
501:
465:
305:
180:
130:
80:
1033:
926:
563:
342:
218:
1058:
1038:
1011:
750:
525:
441:
256:
205:
56:
477:
317:
280:
231:
192:
36:
32:
832:
616:
Frucht, R. (1976), "A canonical representation of trivalent
Hamiltonian graphs",
1043:
368:
330:
155:
114:
60:
24:
692:
416:
404:
380:
133:: this is true if and only if all of the offsets in the LCF notation are odd.
107:
19:
931:
837:
631:
878:
968:
67:. The cycle itself includes two out of the three adjacencies for each
683:
978:
957:
872:
882:
973:
868:
660:(2008), "Hamiltonicity of vertex-transitive graphs of order
759:, Academic Press, Inc. , New York-London, p. 13,
853:, Mathematical Association of America, archived from
94:
is the number of vertices. Entries congruent modulo
1026:
987:
950:
914:
811:
799:
787:
110:, neither of which are permitted in simple graphs.
871:– JavaScript interactive application, built with
894:
8:
869:"Cubic Hamiltonian Graphs from LCF Notation"
79:In a Hamiltonian graph, the vertices can be
901:
887:
879:
682:
593:Configurations from a Graphical Viewpoint
140:
18:
553:
589:"2.3.2 Cubic graphs and LCF notation"
559:
557:
7:
812:Coxeter, Frucht & Powers (1981)
800:Coxeter, Frucht & Powers (1981)
788:Coxeter, Frucht & Powers (1981)
850:Math Games: Cubic Symmetric Graphs
14:
670:European Journal of Combinatorics
568:The many faces of the Nauru graph
847:Ed Pegg Jr. (29 December 2003),
747:Coxeter, Harold Scott MacDonald
16:Representation of cubic graphs
1:
1070:Hamiltonian paths and cycles
1008:for cubic Hamiltonian graphs
59:, for the representation of
1065:Graph description languages
790:, Fig. 1.1, p. 5.
753:; Powers, David L. (1981),
1086:
922:Graph (abstract data type)
693:10.1016/j.ejc.2007.02.002
47:is a notation devised by
1000:Graph Modelling Language
595:, Springer, p. 32,
619:Journal of Graph Theory
632:10.1002/jgt.3190010111
429:Truncated dodecahedral
28:
909:Graph representations
756:Zero-symmetric graphs
539:Extended LCF notation
244:Truncated tetrahedral
22:
1018:Trivial Graph Format
356:Truncated octahedral
294:zero-symmetric graph
585:Servatius, Brigitte
393:Tutte–Coxeter graph
269:Möbius–Kantor graph
81:arranged in a cycle
988:Text-based formats
830:Weisstein, Eric W.
724:2012-03-02 at the
454:Harries–Wong graph
108:multiple adjacency
51:, and extended by
29:
27:has LCF notation .
1052:
1051:
951:XML-based formats
536:
535:
490:Biggs–Smith graph
343:Truncated cubical
65:Hamiltonian cycle
1077:
1027:Related concepts
942:Incidence matrix
937:Adjacency matrix
903:
896:
889:
880:
865:
864:
862:
843:
842:
815:
809:
803:
797:
791:
785:
779:
777:
743:
737:
711:
705:
704:. See Section 2.
703:
686:
666:
654:Kutnar, Klavdija
650:
644:
642:
613:
607:
605:
577:
571:
561:
141:
53:H. S. M. Coxeter
49:Joshua Lederberg
1085:
1084:
1080:
1079:
1078:
1076:
1075:
1074:
1055:
1054:
1053:
1048:
1022:
983:
946:
915:Data structures
910:
907:
860:
858:
846:
828:
827:
824:
819:
818:
810:
806:
798:
794:
786:
782:
767:
751:Frucht, Roberto
745:
744:
740:
726:Wayback Machine
712:
708:
661:
658:Marušič, Dragan
652:
651:
647:
615:
614:
610:
603:
581:Pisanski, TomaĹľ
579:
578:
574:
562:
555:
550:
541:
514:Ljubljana graph
502:Balaban 11-cage
466:Balaban 10-cage
306:Desargues graph
139:
123:
77:
63:that contain a
17:
12:
11:
5:
1083:
1081:
1073:
1072:
1067:
1057:
1056:
1050:
1049:
1047:
1046:
1041:
1036:
1034:Graph database
1030:
1028:
1024:
1023:
1021:
1020:
1015:
1009:
1003:
997:
991:
989:
985:
984:
982:
981:
976:
971:
966:
963:
960:
954:
952:
948:
947:
945:
944:
939:
934:
929:
927:Adjacency list
924:
918:
916:
912:
911:
908:
906:
905:
898:
891:
883:
877:
876:
866:
844:
833:"LCF Notation"
823:
822:External links
820:
817:
816:
804:
792:
780:
765:
738:
706:
677:(2): 423–438,
645:
608:
601:
572:
552:
551:
549:
546:
540:
537:
534:
533:
531:
528:
522:
521:
519:
516:
510:
509:
507:
504:
498:
497:
495:
492:
486:
485:
483:
480:
474:
473:
471:
468:
462:
461:
459:
456:
450:
449:
447:
444:
438:
437:
435:
432:
425:
424:
422:
419:
413:
412:
410:
407:
401:
400:
398:
395:
389:
388:
386:
383:
377:
376:
374:
371:
365:
364:
362:
359:
352:
351:
349:
346:
339:
338:
336:
333:
327:
326:
324:
321:
314:
313:
311:
308:
302:
301:
299:
296:
289:
288:
286:
283:
277:
276:
274:
271:
265:
264:
262:
259:
253:
252:
250:
247:
240:
239:
237:
234:
228:
227:
224:
221:
219:Franklin graph
215:
214:
211:
208:
202:
201:
198:
195:
189:
188:
186:
183:
177:
176:
174:
171:
165:
164:
162:
159:
152:
151:
148:
145:
138:
135:
122:
119:
76:
73:
15:
13:
10:
9:
6:
4:
3:
2:
1082:
1071:
1068:
1066:
1063:
1062:
1060:
1045:
1042:
1040:
1039:Graph drawing
1037:
1035:
1032:
1031:
1029:
1025:
1019:
1016:
1013:
1012:Newick format
1010:
1007:
1004:
1001:
998:
996:
993:
992:
990:
986:
980:
977:
975:
972:
970:
967:
964:
961:
959:
956:
955:
953:
949:
943:
940:
938:
935:
933:
930:
928:
925:
923:
920:
919:
917:
913:
904:
899:
897:
892:
890:
885:
884:
881:
874:
870:
867:
857:on 7 May 2013
856:
852:
851:
845:
840:
839:
834:
831:
826:
825:
821:
814:, p. 12.
813:
808:
805:
802:, p. 54.
801:
796:
793:
789:
784:
781:
776:
772:
768:
766:0-12-194580-4
762:
758:
757:
752:
748:
742:
739:
735:
731:
727:
723:
720:
716:
710:
707:
702:
698:
694:
690:
685:
680:
676:
672:
671:
665:
659:
655:
649:
646:
641:
637:
633:
629:
625:
621:
620:
612:
609:
604:
602:9780817683641
598:
594:
590:
586:
582:
576:
573:
569:
565:
560:
558:
554:
547:
545:
538:
532:
529:
527:
526:Tutte 12-cage
524:
523:
520:
517:
515:
512:
511:
508:
505:
503:
500:
499:
496:
493:
491:
488:
487:
484:
481:
479:
476:
475:
472:
469:
467:
464:
463:
460:
457:
455:
452:
451:
448:
445:
443:
442:Harries graph
440:
439:
436:
433:
430:
427:
426:
423:
420:
418:
415:
414:
411:
408:
406:
403:
402:
399:
396:
394:
391:
390:
387:
384:
382:
379:
378:
375:
372:
370:
367:
366:
363:
360:
357:
354:
353:
350:
347:
344:
341:
340:
337:
334:
332:
329:
328:
325:
322:
319:
316:
315:
312:
309:
307:
304:
303:
300:
297:
295:
291:
290:
287:
284:
282:
279:
278:
275:
272:
270:
267:
266:
263:
260:
258:
257:Heawood graph
255:
254:
251:
248:
245:
242:
241:
238:
235:
233:
230:
229:
225:
222:
220:
217:
216:
212:
209:
207:
206:Bidiakis cube
204:
203:
199:
196:
194:
191:
190:
187:
184:
182:
181:Cubical graph
179:
178:
175:
172:
170:
169:Utility graph
167:
166:
163:
160:
157:
154:
153:
150:LCF notation
149:
146:
143:
142:
136:
134:
132:
127:
120:
118:
116:
111:
109:
105:
101:
97:
93:
89:
86:
82:
74:
72:
70:
66:
62:
58:
57:Robert Frucht
54:
50:
46:
42:
38:
34:
26:
21:
1006:LCF notation
1005:
861:25 September
859:, retrieved
855:the original
849:
836:
807:
795:
783:
755:
741:
709:
684:math/0606585
674:
668:
663:
648:
626:(1): 45–60,
623:
617:
611:
592:
575:
564:Eppstein, D.
542:
478:Foster graph
318:Dodecahedral
281:Pappus graph
232:Frucht graph
193:Wagner graph
128:
124:
121:Applications
112:
99:
98:to 0, 1, or
95:
91:
87:
78:
61:cubic graphs
44:
41:LCF notation
40:
37:graph theory
33:mathematical
30:
1044:Linked data
369:Nauru graph
331:McGee graph
156:Tetrahedral
115:Nauru graph
75:Description
25:Nauru graph
1059:Categories
548:References
417:Gray graph
405:Dyck graph
381:F26A graph
1014:for trees
932:Edge list
838:MathWorld
292:Smallest
131:bipartite
35:field of
722:Archived
719:NetworkX
587:(2013),
213:or or
147:Vertices
137:Examples
90:, where
45:LCF code
969:GraphML
875:library
775:0658666
701:2388379
640:0463029
570:, 2007.
31:In the
773:
763:
732:, and
730:igraph
699:
638:
599:
85:modulo
69:vertex
1002:(GML)
979:XGMML
962:DotML
715:Maple
713:e.g.
679:arXiv
431:graph
358:graph
345:graph
320:graph
246:graph
158:graph
965:GEXF
958:DGML
873:D3js
863:2010
761:ISBN
734:sage
597:ISBN
226:or
200:or
144:Name
104:loop
55:and
23:The
995:DOT
974:GXL
689:doi
667:",
628:doi
530:126
518:112
506:112
494:102
106:or
43:or
1061::
835:.
771:MR
769:,
749:;
728:,
717:,
697:MR
695:,
687:,
675:29
673:,
656:;
636:MR
634:,
622:,
591:,
583:;
566:,
556:^
482:90
470:70
458:70
446:70
434:60
421:54
409:32
397:30
385:26
373:24
361:24
348:24
335:24
323:20
310:20
298:18
285:18
273:16
261:14
249:12
236:12
223:12
210:12
39:,
902:e
895:t
888:v
841:.
778:.
736:.
691::
681::
664:p
662:4
643:.
630::
624:1
606:.
197:8
185:8
173:6
161:4
100:N
96:N
92:N
88:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
