In the mathematical field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by

H. S. M. Coxeter Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century. Biography Coxeter was born in Kensington t ...

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 Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

, 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 In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is t ...

''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 Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...

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 In the mathematics, mathematical field of graph theory, the Nauru graph is a symmetric graph, symmetric bipartite graph, bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag o ...

, shown on the right, has four repetitions of the same six offsets, and can be represented by the LCF notation , −9, 7, −7, 9, −5sup>4. 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 Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

: this is true if and only if all of the offsets in the LCF notation are odd..

Examples

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 , −9, 7, −7, 9, −5sup>4, and so can be written , −9, 7; −sup>4 in the extended notation.

References

External links

* *
"Cubic Hamiltonian Graphs from LCF Notation"
– JavaScript interactive application, built with

D3js D3.js (also known as D3, short for Data-Driven Documents) is a JavaScript library for producing dynamic, interactive data visualizations in web browsers. It makes use of Scalable Vector Graphics (SVG), HTML5, and Cascading Style Sheets (CSS) sta ...

library {{Graph representations Graph description languages Hamiltonian paths and cycles