LCF

LCF notation (Lederberg-Coxeter-Frucht notation) is a compact textual encoding for cubic graphs that contain a Hamiltonian cycle. It was devised by Joshua Lederberg and later extended by H. S. M. Coxeter and Robert Frucht, whose initials give the notation its name. It targets a narrow but important class of structures: 3-regular (every vertex has exactly three incident edges) graphs in which a cycle visits every vertex exactly once.

The data model exploits that Hamiltonian cycle. The cycle already supplies two of the three edges at each vertex, so LCF only needs to record the third edge per vertex. Vertices are laid out in cyclic order and each entry states how many positions along the cycle that vertex's third neighbor lies, positive for clockwise and negative for counter-clockwise. Offsets are read modulo N (the vertex count); entries congruent to 0, 1, or N-1 are disallowed because they would create loops or duplicate the cycle edges, so only simple graphs are expressible. A notation is written as a bracketed sequence such as [5, -9, 7, -7, 9, -5], and a superscript exponent denotes repetition of the block, e.g. that sequence raised to the fourth power yields the 24-vertex Nauru graph. An extended "anti-palindromic" form by Coxeter, Frucht, and Powers compresses a block whose second half mirrors the first with flipped signs, written with a semicolon and dash.

Because it stores only one integer per vertex, LCF is extremely space-efficient and has long been used to publish and catalog symmetric cubic graphs concisely. A useful property is that bipartiteness can be checked directly: the graph is bipartite exactly when all offsets are odd. It also makes generation trivial in software; the notation is a first-class graph generator in tool:networkx (its LCF_graph produces the dodecahedral, Desargues, Heawood, and Pappus graphs) and is likewise supported in tool:igraph, SageMath, and Maple.

Its limitations follow from its specialization. LCF cannot represent non-cubic graphs, graphs lacking a Hamiltonian cycle (such as the Petersen graph), or graphs with loops or parallel edges, and it carries no attributes, weights, or labels. The encoding is also non-unique: a single graph admits many LCF strings depending on the chosen Hamiltonian cycle and starting vertex. For interchange it is usually expanded into a general graph model and re-emitted in a richer format such as format:graphml, format:gml, format:dot, or an edge-list form like format:adjlist.