LCF notation

The Nauru graph[1] has LCF notation [5, −9, 7, −7, 9, −5]4.

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.[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.

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,[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.

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.[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]

Examples

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

Extended LCF notation

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]

References

  1. ^ a b Eppstein, D., The many faces of the Nauru graph, 2007.
  2. ^ Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641.
  3. ^ Frucht, R. (1976), "A canonical representation of trivalent Hamiltonian graphs", Journal of Graph Theory, 1 (1): 45–60, doi:10.1002/jgt.3190010111, MR 0463029.
  4. ^ Kutnar, Klavdija; Marušič, Dragan (2008), "Hamiltonicity of vertex-transitive graphs of order 4p", European Journal of Combinatorics, 29 (2): 423–438, arXiv:math/0606585, doi:10.1016/j.ejc.2007.02.002, MR 2388379. See Section 2.
  5. ^ e.g. Maple, NetworkX Archived 2012-03-02 at the Wayback Machine, igraph, and sage.
  6. ^ Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, p. 13, ISBN 0-12-194580-4, MR 0658666.
  7. ^ Coxeter, Frucht & Powers (1981), Fig. 1.1, p. 5.
  8. ^ Coxeter, Frucht & Powers (1981), p. 54.
  9. ^ Coxeter, Frucht & Powers (1981), p. 12.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.