LCF notation

The Foster graph : If you denote the top node with , then is

{\ displaystyle v_ {0}}

90, [17,-9,37,-37,9,-17], 15

an associated LCF notation.

In combinatorics as a branch of discrete mathematics , the Lederberg-Coxeter-Fruchte notation ( LCF for short ) is a compact representation of finite cubic Hamiltonian graphs . The notation goes back to Joshua Lederberg and was expanded by HSM Coxeter and Robert Frucht . Many programs for manipulating graphs support LCF input.

syntax

Each LCF code has the following form:

 $n,\left[s_{0},s_{1},\dots s_{k}\right],p$

Here is the number of nodes that are elements of a complete system of smallest remainders modulo without the zero (in other words whole numbers from ) and is an iteration parameter, so that . You also write in printed publications . ${\ displaystyle n = | V |}$ ${\ displaystyle s_ {i}}$ ${\ displaystyle n}$ ${\ displaystyle \ left [- \ left \ lfloor {\ frac {| V |} {2}} \ right \ rfloor, \ left \ lfloor {\ frac {| V |} {2}} \ right \ rfloor \ right ] \ setminus \ {0 \} \ subset \ mathbb {Z}}$ ${\ displaystyle p \ in \ mathbb {N}}$ ${\ displaystyle k \ cdot p = n}$ ${\ displaystyle \ left [s_ {0}, s_ {1} \ dots s_ {k} \ right] ^ {p}}$

interpretation: First, a circle of length with nodes is created. Starting at to the chord edges are added to the circle if they do not already exist. Here denotes the modulo operator. ${\ displaystyle n}$ ${\ displaystyle \ {v_ {0}, v_ {1} \ dots v_ {n} \}}$ ${\ displaystyle i = 0}$ ${\ displaystyle i = k \ cdot p}$ ${\ displaystyle \ left (v_ {i}, v _ {(s_ {i ~ \% ~ k}) ~ \% ~ n} \ right)}$ ${\ displaystyle \%}$

A method for calculating an LCF code in reverse to a graph can then be easily constructed. LCF notations for a graph are generally not clearly defined. They depend on the choice of the starting node and on the choice of the Hamilton circle (there you always have at least one choice of orientation). Conversely, there can only be one graph that is unique apart from isomorphism for each LCF notation . If you represent LCF code together with a plot , it is convention to set the nodes, if they are not numbered, along the selected Hamilton circle "circular" (more precisely polygonal ), with the node "at the top". ${\ displaystyle v_ {0}}$ ${\ displaystyle v_ {0}}$

Some plots with LCF codes
The Wagner graph :
```
8, [-4], 8
```
The McGee graph :
```
24, [12,7,-7], 8
```
The Franklin Graph :
```
12, [5,-5], 6
```
The Möbius-Cantor graph :
```
16, [5,-5], 8
```
The Franklin graph: (alternative representation)
```
12, [-5,-3,3,5], 3
```

Web links

Eric W. Weisstein: LCF notation . at MathWorld .

Individual evidence

↑ J. Lederberg: DENDRAL-64: A System for Computer Construction, enumeration and notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II: Topology of Cyclic Graphs. Interim Report to the National Aeronautics and Space Administration. Grant NSG 81-60. December 15, 1965. [1] (PDF)
↑ HSM Coxeter, R. Frucht, DL Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981.
↑ For example Maple , NetworkX with generators.small.LCF_graph , R , sage ( Memento from August 21, 2009 in the Internet Archive ) and probably more.
↑ See documentation for the relevant class from Sage .
↑ Otherwise you can read it here: R. Frucht: A Canonical Representation of Trivalent Hamiltonian Graphs. In: Journal of Graph Theory. 1, 1976, pp. 46-60.

[1] J. Lederberg: DENDRAL-64: A System for Computer Construction, enumeration and notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II: Topology of Cyclic Graphs. Interim Report to the National Aeronautics and Space Administration. Grant NSG 81-60. December 15, 1965. [1] (PDF)

[2] HSM Coxeter, R. Frucht, DL Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981.

[3] For example Maple , NetworkX with generators.small.LCF_graph , R , sage ( Memento from August 21, 2009 in the Internet Archive ) and probably more.

[4] See documentation for the relevant class from Sage .

[5] Otherwise you can read it here: R. Frucht: A Canonical Representation of Trivalent Hamiltonian Graphs. In: Journal of Graph Theory. 1, 1976, pp. 46-60.