LCF code

The Nauru graph ^[1] has an LCF code [5, −9, 7, −7, 9, −5] ⁴ .

LCF code is a notation system in combinatorial mathematics developed by Lederberg and expanded by Coxeter and to represent cubic graphs that are Hamiltonian ^[2] ^[3] . Since the graphs are Hamiltonian, the vertices can be , which defines two edges for each vertex. The third rib can now be described by the number of positions at which the end of the rib is spaced from the beginning (with plus clockwise and minus counterclockwise). Often as a result we get a repeating sequence of numbers, in this case only this repeating part is written out, and the number of repetitions is shown by a superscript (like a degree). For example, the Nauru Count ^[1] has an LCF code [5, −9, 7, −7, 9, −5] ⁴ . The same graph can have different LCF codes, depending on how the vertices are located on the circle (the graph can have several variants of the Hamiltonian cycle).

Numbers inside square brackets are considered modulo $N$ ${\ displaystyle N}$ $N$ where $N$ ${\ displaystyle N}$ $N$ - the number of vertices of the graph. Numbers comparable modulo $N$ ${\ displaystyle N}$ $N$ with 0, 1, and $N-1$ ${\ displaystyle N-1}$ $N-1$ not allowed ^[4] , since they cannot correspond to any third rib.

The LCF code is useful for a concise description of Hamiltonian cubic graphs, in particular those shown in the table below. In addition, some graph software packages include utilities for creating a graph from its LCF code ^[5] .

Examples

Title	Top	LCF code
Count tetrahedron	four	[2] ⁴
$K_{3,3}$ ${\ displaystyle K_ {3,3}}$	6	[3] ⁶
Cube graph	eight	[3, -3] ⁴
Count Wagner	eight	[4] ⁸ or [4, -3,3,4] ²
	12	[6.4, -4] ⁴ or [6, -3,3,6,3, -3] ² or [-3,6,4, -4,6,3, -4,6, -3, 3,6,4]
Count Franklin	12	[5, -5] ⁶ or [-5, -3,3,5] ³
Count Frucht	12	[-5, -2, -4,2,5, -2,2,5, -2, -5,4,2]
Count of truncated tetrahedron	12	[2.6, -2] ⁴
Earl of Howwood	14	[5, -5] ⁷
Earl of Mobius - Cantor	sixteen	[5, -5] ⁸
Count Pappa	18	[5.7, -7.7, -7, -5] ³
Count of Desargues	20	[5, -5.9, -9] ⁵
Dodecahedron count	20	[10,7,4, -4, -7,10, -4,7, -7,4] ²
Count McGee	24	[12.7, -7] ⁸
Truncated Cube Count	24	[2.9, -2.2, -9, -2] ⁴
Count truncated octahedron	24	[3, -7.7, -3] ⁶
Count of Nauru	24	[5, -9.7, -7.9, -5] ⁴
Count F26A	26	[-7, 7] ¹³
Count Tatta - Coxeter	thirty	[-13, -9.7, -7.9.13] ⁵
Count Dick	32	[5, -5.13, -13] ⁸
Earl Gray	54	[-25.7, -7.13, -13.25] ⁹
The truncated dodecahedron count	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] ²
Earl of Harris	70	[-29, -19, -13,13,21, -27,27,33, -13,13,19, -21, -33,29] ⁵
	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]
	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]
Count Foster	90	[17, -9.37, -37.9, -17] ¹⁵
	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]
11th Balaban Cell	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]
Count Ljubljana	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] ²
12-Tatt Cell	126	[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17] ⁷

Generic LCF Code

A more complex version of the LCF code was proposed by Coxeter, Frucht and Powers in a later paper ^[6] . In particular, they proposed an “anti-palidromic” code - if the second half of the numbers inside the square brackets is the inverse sequence of the first part with the signs reversed, then the second part is replaced with a semicolon and a dash. The Nauru graph satisfies this condition, so that its code [5, −9, 7, −7, 9, −5] ⁴ in a generalized form can be written as [5, −9, 7; -] ⁴ ^[7] .

Notes

↑ ¹ ² , The many faces of the Nauru graph Archived July 21, 2011. LiveJournal 2007
↑ Tomaž Pisanski, Brigitte Servatius. Configurations from a Graphical Viewpoint. - Springer, 2013 .-- ISBN 9780817683641 .
↑ R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. - 1976. - T. 1 , no. 1 . - S. 45-60 . - DOI : 10.1002 / jgt.3190010111 .
↑ Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 p // European Journal of Combinatorics. - T. 29 , no. 2 (February 2008) . - S. 423-438, section 2 ..
↑ e.g. Maple , NetworkX Archived March 2, 2012 to Wayback Machine , R , and sage .
↑ Coxeter, Frucht, Powers, 1981 , p. 54
↑ Coxeter, Frucht, Powers, 1981 , p. 12

Links

HSM Coxeter, R. Frucht, DL Powers. Zero-symmetric graphs: trivalent graphical regular representations of groups. - Academic Press, 1981. - ISBN 0-12-194580-4 .
Weisstein, Eric W. LCF Notation at Wolfram MathWorld .
Ed Pegg Jr. Math Games: Cubic Symmetric Graphs. - December 29, 2003.
Cubic Hamiltonian Graphs from LCF Notation is an interactive application (in JavaScript) built with the D3js library

[DE1-1] ¹ ² , The many faces of the Nauru graph Archived July 21, 2011. LiveJournal 2007

[2] Tomaž Pisanski, Brigitte Servatius. Configurations from a Graphical Viewpoint. - Springer, 2013 .-- ISBN 9780817683641 .

[3] R. Frucht. A canonical representation of trivalent Hamiltonian graphs // Journal of Graph Theory. - 1976. - T. 1 , no. 1 . - S. 45-60 . - DOI : 10.1002 / jgt.3190010111 .

[4] Klavdija Kutnar, Dragan Marušič. Hamiltonicity of vertex-transitive graphs of order 4 p // European Journal of Combinatorics. - T. 29 , no. 2 (February 2008) . - S. 423-438, section 2 ..

[5] .g. Maple , NetworkX Archived March 2, 2012 to Wayback Machine , R , and sage .

[6] Coxeter, Frucht, Powers, 1981 , p. 54

[7] Coxeter, Frucht, Powers, 1981 , p. 12

LCF code

Examples

Generic LCF Code

Notes

Links

More articles: