LCF notation
Introduction The Nauru graph has LCF notation .In the mathematical field of graph theory, '''LCF notation''' or '''LCF code''' is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle itself includes two out of the three adjacencies for each vertex, 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.
Description In a Hamiltonian graph, 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. 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 modulo ''N'', where ''N'' is the number of vertices. Entries congruent modulo ''N'' to 0, 1, or ''N'' − 1 do not appear in this sequence of numbers, because they would correspond either to a loop or multiple adjacency, neither of which are permitted in simple graphs.Often the pattern repeats, and the number of repetitions can be indicated by a superscript in the notation. For example, the Nauru graph, shown on the right, has four repetitions of the same six offsets, and can be represented by the LCF notation 5, −9, 7, −7, 9, −54.A single graph may have multiple different LCF notations, depending on the choices of Hamiltonian cycle and starting vertex.
Applications 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.If a graph is represented by LCF notation, it is straightforward to test whether the graph is bipartite: this is true if and only if all of the offsets in the LCF notation are odd.
Examples Name  Vertices  LCF notationTetrahedral graph  4  24Utility graph  6  36Cubical graph  8  3,−34Wagner graph  8  48 or 4,−3,3,42Bidiakis cube  12  6,4,−44 or 6,−3,3,6,3,−32 or −3,6,4,−4,6,3,−4,6,−3,3,6,4Franklin graph  12  5,−56 or −5,−3,3,53Frucht graph  12  −5,−2,−4,2,5,−2,2,5,−2,−5,4,2Truncated tetrahedral graph  12  2,6,−24Heawood graph  14  5,−57Möbius–Kantor graph  16  5,−58Pappus graph  18  5,7,−7,7,−7,−53Smallest zero-symmetric graph  18  5,−59Desargues graph  20  5,−5,9,−95Dodecahedral graph  20  10,7,4,−4,−7,10,−4,7,−7,42McGee graph  24  12,7,−78Truncated cubical graph  24  2,9,−2,2,−9,−24Truncated octahedral graph  24  3,−7,7,−36Nauru graph  24  5,−9,7,−7,9,−54F26A graph  26  −7, 713Tutte–Coxeter graph  30  −13,−9,7,−7,9,135Dyck graph  32  5,−5,13,−138Gray graph  54  −25,7,−7,13,−13,259Truncated 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, 22Harries graph  70  −29,−19,−13,13,21,−27,27,33,−13,13,19,−21,−33,295Harries–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, −25Balaban 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, 29Foster graph  90  17,−9,37,−37,9,−1715Biggs–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, 37Balaban 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, 16Ljubljana 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, −392Tutte 12-cage  126  17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −177
Extended LCF notation 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, then it was replaced by a semicolon and a dash. The Nauru graph satisfies this condition with 5, −9, 7, −7, 9, −54, and so can be written 5, −9, 7; −4 in the extended notation.
References
External links * * *  "Cubic Hamiltonian Graphs from LCF Notation" – JavaScript interactive application, built with D3js library