LCF notation
In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian.[2][3] Since the graphs are Hamiltonian, the vertices can be arranged in a cycle, 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. Often the pattern repeats, which is indicated by a superscript in the notation. For example, the Nauru graph,[1] shown on the right, has LCF notation [5, −9, 7, −7, 9, −5]4. Graphs may have different LCF notations, depending on precisely how the vertices are arranged.
The numbers between the square brackets are interpreted modulo N, where N is the number of vertices. Entries equal (modulo N) to 0, 1, and N−1 are not permitted,[4] since they do not correspond to valid third edges.
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.[5]
Examples
| Name | Vertices | LCF notation |
| Tetrahedral graph | 4 | [2]4 |
| Utility graph | 6 | [3]6 |
| Cubical graph | 8 | [3,-3]4 |
| Wagner graph | 8 | [4]8 or [4,-3,3,4]2 |
| Bidiakis cube | 12 | [6,4,-4]4 or [6,-3,3,6,3,-3]2 or [-3,6,4,-4,6,3,-4,6,-3,3,6,4] |
| Franklin graph | 12 | [5,-5]6 or [-5,-3,3,5]3 |
| Frucht graph | 12 | [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2] |
| Truncated tetrahedral graph | 12 | [2,6,-2]4 |
| Heawood graph | 14 | [5,-5]7 |
| Mobius-Kantor graph | 16 | [5,-5]8 |
| Pappus graph | 18 | [5,7,-7,7,-7,-5]3 |
| Desargues graph | 20 | [5,-5,9,-9]5 |
| Dodecahedral graph | 20 | [10,7,4,-4,-7,10,-4,7,-7,4]2 |
| McGee graph | 24 | [12,7,-7]8 |
| Truncated cubical graph | 24 | [2,9,-2,2,-9,-2]4 |
| Truncated octahedral graph | 24 | [3,-7,7,-3]6 |
| Nauru graph | 24 | [5,-9,7,-7,9,-5]4 |
| F26A graph | 26 | [-7, 7]13 |
| Tutte–Coxeter graph | 30 | [-13,-9,7,-7,9,13]5 |
| Dyck graph | 32 | [5,-5,13,-13]8 |
| Gray graph | 54 | [-25,7,-7,13,-13,25]9 |
| Truncated dodecahedral graph | 60 | [30, -2, 2, 21, -2, 2, 12, -2, 2, -12, -2, 2, -21, -2, 2, 30, -2, 2, -12, -2, 2, 21, -2, 2, -21, -2, 2, 12, -2, 2]2 |
| Harries graph | 70 | [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]5 |
| Harries–Wong graph | 70 | [9, 25, 31, -17, 17, 33, 9, -29, -15, -9, 9, 25, -25, 29, 17, -9, 9, -27, 35, -9, 9, -17, 21, 27, -29, -9, -25, 13, 19, -9, -33, -17, 19, -31, 27, 11, -25, 29, -33, 13, -13, 21, -29, -21, 25, 9, -11, -19, 29, 9, -27, -19, -13, -35, -9, 9, 17, 25, -9, 9, 27, -27, -21, 15, -9, 29, -29, 33, -9, -25] |
| Balaban 10-cage | 70 | [-9, -25, -19, 29, 13, 35, -13, -29, 19, 25, 9, -29, 29, 17, 33, 21, 9,-13, -31, -9, 25, 17, 9, -31, 27, -9, 17, -19, -29, 27, -17, -9, -29, 33, -25,25, -21, 17, -17, 29, 35, -29, 17, -17, 21, -25, 25, -33, 29, 9, 17, -27, 29, 19, -17, 9, -27, 31, -9, -17, -25, 9, 31, 13, -9, -21, -33, -17, -29, 29] |
| Foster graph | 90 | [17,-9,37,-37,9,-17]15 |
| Biggs-Smith graph | 102 | [16, 24, -38, 17, 34, 48, -19, 41, -35, 47, -20, 34, -36, 21, 14, 48, -16, -36, -43, 28, -17, 21, 29, -43, 46, -24, 28, -38, -14, -50, -45, 21, 8, 27, -21, 20, -37, 39, -34, -44, -8, 38, -21, 25, 15, -34, 18, -28, -41, 36, 8, -29, -21, -48, -28, -20, -47, 14, -8, -15, -27, 38, 24, -48, -18, 25, 38, 31, -25, 24, -46, -14, 28, 11, 21, 35, -39, 43, 36, -38, 14, 50, 43, 36, -11, -36, -24, 45, 8, 19, -25, 38, 20, -24, -14, -21, -8, 44, -31, -38, -28, 37] |
| Balaban 11-cage | 112 | [44, 26, -47, -15, 35, -39, 11, -27, 38, -37, 43, 14, 28, 51, -29, -16, 41, -11, -26, 15, 22, -51, -35, 36, 52, -14, -33, -26, -46, 52, 26, 16, 43, 33, -15, 17, -53, 23, -42, -35, -28, 30, -22, 45, -44, 16, -38, -16, 50, -55, 20, 28, -17, -43, 47, 34, -26, -41, 11, -36, -23, -16, 41, 17, -51, 26, -33, 47, 17, -11, -20, -30, 21, 29, 36, -43, -52, 10, 39, -28, -17, -52, 51, 26, 37, -17, 10, -10, -45, -34, 17, -26, 27, -21, 46, 53, -10, 29, -50, 35, 15, -47, -29, -41, 26, 33, 55, -17, 42, -26, -36, 16] |
| Ljubljana graph | 112 | [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]2 |
| Tutte 12-cage | 126 | [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17]7 |
Extended LCF notation
A more complex extended version of LCF notation was provided by Coxeter, Frucht, and Powers in later work.[6] 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, then it was replaced by a semicolon and a dash. The Nauru graph satisfies this condition with [5, −9, 7, −7, 9, −5]4, and so can be written [5, −9, 7; −]4 in the extended notation.[7]
References
- ^ a b Eppstein, D., The many faces of the Nauru graph on LiveJournal, 2007.
- ^ Weisstein, Eric W. "LCF Notation." From MathWorld--A Wolfram Web Resource.
- ^ Frucht, R. (1976), "A canonical representation of trivalent Hamiltonian graphs", Journal of Graph Theory, 1 (1): 45–60, doi:10.1002/jgt.3190010111.
- ^ Klavdija Kutnar and Dragan Marušič, "Hamiltonicity of vertex-transitive graphs of order 4p," European Journal of Combinatorics, Volume 29, Issue 2 (February 2008), pp. 423-438, section 2.
- ^ e.g. Maple, NetworkX, R, and sage.
- ^ Coxeter, H. S. M.; Frucht, R.; Powers, D. L. (1981). Zero-symmetric graphs: trivalent graphical regular representations of groups. Academic Press. p. 54. ISBN 0-12-194580-4.
- ^ Coxeter, Frucht, Powers, p. 12.
External links
- Weisstein, Eric W. "LCF Notation". MathWorld.
- Ed Pegg Jr. (29 December 2003). "Math Games: Cubic Symmetric Graphs". Mathematical Association of America.
- "Cubic Hamiltonian Graphs from LCF Notation" - JavaScript interactive application, built with D3js library