Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
LCF notation
open-in-new
<h2 id="description">Description</h2> <p>In a Hamiltonian graph, the vertices can be <a href="/facts/Circular_layout/41o5E5my">arranged in a cycle</a>, 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 <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> <i>N</i>, where <i>N</i> is the number of vertices. Entries congruent modulo <i>N</i> to 0, 1, or <i>N</i> − 1 do not appear in this sequence of numbers,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> because they would correspond either to a <a href="/facts/Loop_(graph_theory)/jCuevIad">loop</a> or <a href="/facts/Multigraph/udmS0Cp0">multiple adjacency</a>, neither of which are permitted in simple graphs. </p><p>Often the pattern repeats, and the number of repetitions can be indicated by a superscript in the notation. For example, the <a href="/facts/Nauru_graph/n9Mgs9Kx">Nauru graph</a>,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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. </p> <h2 id="applications">Applications</h2> <p>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.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>If a graph is represented by LCF notation, it is straightforward to test whether the graph is <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite</a>: this is true if and only if all of the offsets in the LCF notation are odd.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="examples">Examples</h2> <table><tbody><tr><th>Name</th><th>Vertices</th><th>LCF notation</th></tr><tr><td><a href="/facts/Tetrahedron/7mkSrl6j">Tetrahedral</a> graph</td><td>4</td><td>[2]4</td></tr><tr><td><a href="/facts/Water%2c_gas%2c_and_electricity/CQQqp6fA">Utility graph</a></td><td>6</td><td>[3]6</td></tr><tr><td><a href="/facts/Hypercube_graph/pwfGEl9J">Cubical graph</a></td><td>8</td><td>[3,−3]4</td></tr><tr><td><a href="/facts/Wagner_graph/TEewcVJN">Wagner graph</a></td><td>8</td><td>[4]8 or [4,−3,3,4]2</td></tr><tr><td><a href="/facts/Bidiakis_cube/SncdbNeI">Bidiakis cube</a></td><td>12</td><td>[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]</td></tr><tr><td><a href="/facts/Franklin_graph/XFqxcrB4">Franklin graph</a></td><td>12</td><td>[5,−5]6 or [−5,−3,3,5]3</td></tr><tr><td><a href="/facts/Frucht_graph/x46IJtNX">Frucht graph</a></td><td>12</td><td>[−5,−2,−4,2,5,−2,2,5,−2,−5,4,2]</td></tr><tr><td><a href="/facts/Truncated_tetrahedron/K9ItvmUK">Truncated tetrahedral</a> graph</td><td>12</td><td>[2,6,−2]4</td></tr><tr><td><a href="/facts/Heawood_graph/ymqQSkIK">Heawood graph</a></td><td>14</td><td>[5,−5]7</td></tr><tr><td><a href="/facts/M%25C3%25B6bius%25E2%2580%2593Kantor_graph/T7NyYuxL">Möbius–Kantor graph</a></td><td>16</td><td>[5,−5]8</td></tr><tr><td><a href="/facts/Pappus_graph/w40dHpA6">Pappus graph</a></td><td>18</td><td>[5,7,−7,7,−7,−5]3</td></tr><tr><td>Smallest <a href="/facts/Zero-symmetric_graph/Docr6aaM">zero-symmetric graph</a>[7]</td><td>18</td><td>[5,−5]9</td></tr><tr><td><a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a></td><td>20</td><td>[5,−5,9,−9]5</td></tr><tr><td><a href="/facts/Dodecahedron/7r519eCl">Dodecahedral</a> graph</td><td>20</td><td>[10,7,4,−4,−7,10,−4,7,−7,4]2</td></tr><tr><td><a href="/facts/McGee_graph/2wcf2bdG">McGee graph</a></td><td>24</td><td>[12,7,−7]8</td></tr><tr><td><a href="/facts/Truncated_cube/XVAUG4fD">Truncated cubical</a> graph</td><td>24</td><td>[2,9,−2,2,−9,−2]4</td></tr><tr><td><a href="/facts/Truncated_octahedron/GA98b4TH">Truncated octahedral</a> graph</td><td>24</td><td>[3,−7,7,−3]6</td></tr><tr><td><a href="/facts/Nauru_graph/n9Mgs9Kx">Nauru graph</a></td><td>24</td><td>[5,−9,7,−7,9,−5]4</td></tr><tr><td><a href="/facts/F26A_graph/WAPDmpox">F26A graph</a></td><td>26</td><td>[−7, 7]13</td></tr><tr><td><a href="/facts/Tutte%25E2%2580%2593Coxeter_graph/SH13hLkX">Tutte–Coxeter graph</a></td><td>30</td><td>[−13,−9,7,−7,9,13]5</td></tr><tr><td><a href="/facts/Dyck_graph/7mHtc5r6">Dyck graph</a></td><td>32</td><td>[5,−5,13,−13]8</td></tr><tr><td><a href="/facts/Gray_graph/Xgfh4m3X">Gray graph</a></td><td>54</td><td>[−25,7,−7,13,−13,25]9</td></tr><tr><td><a href="/facts/Truncated_dodecahedron/PVTAsUWQ">Truncated dodecahedral</a> graph</td><td>60</td><td>[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</td></tr><tr><td><a href="/facts/Harries_graph/QwwrzAfM">Harries graph</a></td><td>70</td><td>[−29,−19,−13,13,21,−27,27,33,−13,13,19,−21,−33,29]5</td></tr><tr><td><a href="/facts/Harries%25E2%2580%2593Wong_graph/dqawcH1S">Harries–Wong graph</a></td><td>70</td><td>[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]</td></tr><tr><td><a href="/facts/Balaban_10-cage/fK4cuLWk">Balaban 10-cage</a></td><td>70</td><td>[−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]</td></tr><tr><td><a href="/facts/Foster_graph/f5Clb9vA">Foster graph</a></td><td>90</td><td>[17,−9,37,−37,9,−17]15</td></tr><tr><td><a href="/facts/Biggs%25E2%2580%2593Smith_graph/UDEzxCPI">Biggs–Smith graph</a></td><td>102</td><td>[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]</td></tr><tr><td><a href="/facts/Balaban_11-cage/ynWe8HYn">Balaban 11-cage</a></td><td>112</td><td>[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]</td></tr><tr><td><a href="/facts/Ljubljana_graph/YIjevVKE">Ljubljana graph</a></td><td>112</td><td>[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</td></tr><tr><td><a href="/facts/Tutte_12-cage/NrkGdHjh">Tutte 12-cage</a></td><td>126</td><td>[17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7</td></tr></tbody></table> <h2 id="extended-lcf-notation">Extended LCF notation</h2> <p>A more complex extended version of LCF notation was provided by Coxeter, Frucht, and Powers in later work.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> 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.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="external-links">External links</h2> <ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/LCFNotation.html">"LCF Notation"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li> <li>Ed Pegg Jr. (29 December 2003), <a href="https://web.archive.org/web/20130507063023/http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html"><i>Math Games: Cubic Symmetric Graphs</i></a>, Mathematical Association of America, archived from <a href="http://www.maa.org/editorial/mathgames/mathgames_12_29_03.html">the original</a> on 7 May 2013, retrieved 25 September 2010</li> <li><a href="http://bl.ocks.org/1703449">"Cubic Hamiltonian Graphs from LCF Notation"</a> – JavaScript interactive application, built with <a href="/facts/D3js/H5xQ0vcu">D3js</a> library</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641. <a href="9780817683641" target="_blank">9780817683641</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="/wiki/Journal_of_Graph_Theory" target="_blank">/wiki/Journal_of_Graph_Theory</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="/wiki/Klavdija_Kutnar" target="_blank">/wiki/Klavdija_Kutnar</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Eppstein, D., The many faces of the Nauru graph, 2007. <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>e.g. Maple, NetworkX Archived 2012-03-02 at the Wayback Machine, igraph, and sage. <a href="http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GraphTheory/SpecialGraphs/LCFGraph" target="_blank">http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GraphTheory/SpecialGraphs/LCFGraph</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="0-12-194580-4" target="_blank">0-12-194580-4</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Coxeter, Frucht & Powers (1981), p. 54. - 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 <a href="https://books.google.com/books?id=2BHjBQAAQBAJ&pg=PA13" target="_blank">https://books.google.com/books?id=2BHjBQAAQBAJ&pg=PA13</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Coxeter, Frucht & Powers (1981), p. 12. - 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 <a href="https://books.google.com/books?id=2BHjBQAAQBAJ&pg=PA13" target="_blank">https://books.google.com/books?id=2BHjBQAAQBAJ&pg=PA13</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>