ArticleslgStudy

science

LCF notation

LCF notation is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand LCF notation rather than just read about it. In short: In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S.

LCF notation — main illustration
LCF notation — illustration

Key takeaways

  • LCF notation belongs to science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect LCF notation to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of LCF notation from memory before moving on to harder problems.

Reference excerpt

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

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

References

External links Weisstein, Eric W. "LCF Notation". MathWorld. Ed Pegg Jr. (29 December 2003), Math Games: Cubic Symmetric Graphs, Mathematical Association of America, archived from the original on 7 May 2013, retrieved 25 September 2010 "Cubic Hamiltonian Graphs from LCF Notation" – JavaScript interactive application, built with D3js library

Illustrations

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

Worked examples

Example 1 — a first encounter with LCF notation

Start with the simplest possible case. Write down what LCF notation claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to LCF notation before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about LCF notation ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of LCF notation

In research
LCF notation appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses LCF notation in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
LCF notation is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph description languages, Hamiltonian paths and cycles, so understanding it makes those chapters shorter.
In everyday life
Look for LCF notation outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study LCF notation in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what LCF notation means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain LCF notation out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is LCF notation in simple terms?

In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S.

Why does LCF notation matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study LCF notation?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on LCF notation.

Tags

  • Graph description languages
  • Hamiltonian paths and cycles

Keep exploring