![The Nauru graph has LCF notation [5, -9, 7, -7, 9, -5] . Nauru graph LCF.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Nauru_graph_LCF.svg/330px-Nauru_graph_LCF.svg.png)
In combinatorial mathematics, 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. [2] [3] 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.
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, [4] 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, [1] 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, −5]4. A single graph may have multiple different LCF notations, depending on the choices of Hamiltonian cycle and starting vertex.
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]
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. [6]
| 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 |
| Möbius–Kantor graph | 16 | [5,−5]8 |
| Pappus graph | 18 | [5,7,−7,7,−7,−5]3 |
| Smallest zero-symmetric graph [7] | 18 | [5,−5]9 |
| 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 |
A more complex extended version of LCF notation was provided by Coxeter, Frucht, and Powers in later work. [8] 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. [9]
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.
In geometry, the truncated octahedron is an Archimedean solid. It has 14 faces, 36 edges, and 24 vertices. Since each of its faces has point symmetry the truncated octahedron is a zonohedron. It is also the Goldberg polyhedron GIV(1,1), containing square and hexagonal faces. Like the cube, it can tessellate 3-dimensional space, as a permutohedron.
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.
In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.
In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered simple convex polyhedra.
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.
In the mathematical field of graph theory, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939.
In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.
In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.
In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel.
Robert Wertheimer Frucht was a German-Chilean mathematician; his research specialty was graph theory and the symmetries of graphs.
The connected 3-regular (cubic) simple graphs are listed for small vertex numbers.
In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge.