Notazione LCF
# Notazione LCF

In matematica combinatoria, la notazione LCF o codice LCF è una notazione ideata da Joshua Lederberg ed estesa da Coxeter e Frucht, per la rappresentazione dei grafi cubici che sono hamiltoniani. Poiché i grafi sono hamiltoniani, i vertici possono essere disposti in cerchio, che corrisponde a due spigoli per vertice. Il terzo spigolo di ciascun vertice può essere descritto allora dal numero di posizioni che esso conduce in senso orario (positivo) o antiorario (negativo). Spesso il modello si ripete, il che è da un apice nella notazione. Per esempio, il grafo di Nauru, mostrato a destra, ha la notazione LCF [5, −9, 7, −7, 9, $−5]^4.$ I grafi possono avere diverse notazioni LCF, a seconda di come precisamente sono disposti i vertici.

I numeri tra parentesi quadre sono interpretate come modulo N, dove N è il numero dei vertici. Gli inserimenti uguali (modulo N) a 0, 1, e N−1 non sono permessi. poiché non corrispondono a terzi spigoli validi.

La notazione LCF è utile per pubblicare descrizioni concise dei grafi cubici hamiltoniani, come gli esempi sottostanti. Inoltre, alcuni pacchetti di programmi per manipolare grafi includono utilità per creare un grafo partendo dalla sua notazione LCF.

## Esempi

| Nome | Vertici | Notazione LCF |
| - | - | - |
| Grafo tetraedrico | 4 | $[2]^4$ |
| Grafo dei servizi pubblici | 6 | $[3]^6$ |
| Grafo cubico | 8 | $[3,-3]^4$ |
| Grafo di Wagner | 8 | $[4]^8$ or $[4,-3,3,4]^2$ |
| Cubo di Bidiakis | 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] |
| Grafo di Franklin | 12 | $[5,-5]^6$ or $[-5,-3,3,5]^3$ |
| Grafo di Frucht | 12 | [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2] |
| Grafo tetraedrico troncato | 12 | $[2,6,-2]^4$ |
| Grafo di Heawood | 14 | $[5,-5]^7$ |
| Grafo di Möbius-Kantor | 16 | $[5,-5]^8$ |
| Grafo di Pappus | 18 | $[5,7,-7,7,-7,-5]^3$ |
| Grafo di Desargues | 20 | $[5,-5,9,-9]^5$ |
| Grafo dodecaedrico | 20 | $[10,7,4,-4,-7,10,-4,7,-7,4]^2$ |
| Grafo di McGee | 24 | $[12,7,-7]^8$ |
| Grafo cubico | 24 | $[2,9,-2,2,-9,-2]^4$ |
| Grafo ottaedrico troncato | 24 | $[3,-7,7,-3]^6$ |
| Grafo di Nauru | 24 | $[5,-9,7,-7,9,-5]^4$ |
| Grafo F26A | 26 | [-7, $7]^{13}$ |
| Grafo di Tutte-Coxeter | 30 | $[-13,-9,7,-7,9,13]^5$ |
| Grafo di Dyck | 32 | $[5,-5,13,-13]^8$ |
| Grafo di Gray | 54 | $[-25,7,-7,13,-13,25]^9$ |
| Grafo dodecaedrico troncato | 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$ |
| Grafo di Harries | 70 | $[-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]^5$ |
| Grafo di Harrie-Wong | 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] |
| Gabbia 10 di Balaban | 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] |
| Grafo di Foster | 90 | $[17,-9,37,-37,9,-17]^{15}$ |
| Grafo di Biggs-Smith | 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] |
| Gabbia 11 di Balaban | 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] |
| Grafo di 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]^2$ |
| Gabbia 12 di Tutte | 126 | [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, $-17]^7$ |

## Notazione LCF estesa

Una versione estesa, più complessa, della notazione LCF fu fornita da Coxeter, Frucht e Powers in un lavoro successivo. In particolare, essi introdussero una notazione "anti-palindromica": se la seconda metà dei numeri tra parentesi quadre era l'inverso della prima metà, ma con tutti i segni cambiati, allora era sostituita da un punto e virgola e da un trattino. Il grafo di Nauru soddisfa questa condizione con [5, −9, 7, −7, 9, $−5]^4,$ e perciò può essere scritto [5, −9, 7; $−]^4$ nella notazione estesa.

