LCF Notation

LCF notation is a concise and convenient notation devised by Joshua Lederberg (winner of the 1958 Nobel Prize in Physiology and Medicine) for the representation of cubic Hamiltonian graphs (Lederberg 1965). The notation was subsequently modified by Frucht (1976) and Coxeter et al. (1981), and hence was dubbed "LCF notation" by Frucht (1976). Pegg (2003) used the notation to describe many of the cubic symmetric graphs. The notation only applies to Hamiltonian graphs, since it achieves its symmetry and conciseness by placing a Hamiltonian cycle in a circular embedding and then connecting specified pairs of nodes with edges.

For example, the notation  describes the cubical graph illustrated above. To see how this works, begin with the cycle graph . Beginning with a vertex , count three vertices clockwise () to  and connect it to  with an edge. Now advance to , count three vertices counterclockwise () to vertex , and connect  and  with an edge. This is one iteration of the process , which is then repeated three more times (for a total of four, corresponding to the exponent of ) until the original vertex is reached, thus giving the graph represented by . Note that the graph is actually traversed two times in this process since each edge is constructed twice, once in each direction.

The LCF notation for a given graph is not unique, since it may be shifted any number of positions to the left or right, or may be reversed (with a corresponding sign change of the entries to correspond to the fact that the numbering of the outer cycle must be done in the opposite order as well). In addition, for a graph with more than one Hamiltonian cycle, different choices are possible for which cycle is mapped to the outer cycle.

As a result, depending on the structure of Hamiltonian cycles, a single graph may have several different LCF notations with different exponents corresponding to different embeddings. Furthermore, inequivalent notations with the same exponent may also exist. For example, the cubic vertex-transitive graph on 18 nodes illustrated above has the four LCF notations , , , , and [, , 5, 9, , 5, 9, , 5, 7, , 7, 9, , 5, 9, , 5].

The following table gives the simplest (i.e., shortest) LCF notations for named cubic Hamiltonian graphs on 20 or fewer nodes. Here,  denotes a cubic symmetric graph on  nodes.

vertices	graph	"minimal" LCF notation
4	tetrahedral graph
6	utility graph
6	3-prism graph
8	cubical graph
8	3-matchstick graph
8	4-Möbius ladder
10	5-Möbius ladder
10	5-prism graph
12	Franklin graph
12	Frucht graph
12	generalized Petersen graph (6,2)
12	6-Möbius ladder
12	6-prism graph
12	truncated tetrahedral graph
14	generalized Petersen graph (7, 2)
14	Heawood graph
14	7-Möbius ladder
14	7-prism graph
16	cubic vertex-transitive graph Ct19
16	Möbius-Kantor graph
16	8-Möbius ladder
16	8-prism graph
18	Pappus graph
18	cubic vertex-transitive graph Ct20
18	cubic vertex-transitive graph Ct23
18	generalized Petersen graph (9,2)
18	generalized Petersen graph (9,3)
18	9-Möbius ladder
18	9-prism graph
20	cubic vertex-transitive graph Ct25
20	cubic vertex-transitive graph Ct28
20	cubic vertex-transitive graph Ct29
20	Desargues graph
20	dodecahedral graph
20	generalized Petersen graph (10, 4)
20	largest cubic nonplanar graph with diameter 3
20	10-Möbius ladder
20	10-prism graph

REFERENCES

Coxeter, H. S. M.; Frucht, R.; and Powers, D. L. Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. New York: Academic Press, 1981.

Frucht, R. "A Canonical Representation of Trivalent Hamiltonian Graphs." J. Graph Th. 1, 45-60, 1976.

Grünbaum, B. Convex Polytopes. New York: Wiley, pp. 362-364, 1967.

Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.

Pegg, E. Jr. "Math Games: Cubic Symmetric Graphs." Dec. 30, 2003. http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html.