Grafo di Petersen generalizzato

Nella teoria dei grafi, i grafi di Petersen generalizzati sono una famiglia di grafi cubici formati connettendo i vertici di un poligono regolare ai vertici corrispondenti di un poligono a stella. Essi includono il grafo di Petersen e generalizzano uno dei modi di costruire quest'ultimo. La famiglia dei grafi di Petersen generalizzati fu introdotta nel 1950 da H. S. M. Coxeter^[1] e a questi grafi nel 1969 fu dato il loro nome da Mark Watkins.^[2]

Definizione e notazione

Nella notazione di Watkins, G(n,k) è un grafo con insieme dei vertici

{u₀, u₁, ..., u_n−1, v₀, v₁, ..., v_n−1}

e insieme degli spigoli

{u_i u_i+1, u_i v_i, v_i v_i+k: i = 0,...,n − 1}

dove i pedici devono essere letti modulo n e k < n/2. La notazione di Coxeter per lo stesso grafo sarebbe {n}+{n/k}, una combinazione dei simboli di Schläfli per gli n-goni regolari e il poligono a stella da cui il grafo è formato. Qualsiasi grafo di Petersen generalizzato può essere costruito anche come un grafo di voltaggio da un grafo con due vertici, due auto-cappi e un altro spigolo.^[3]

Lo stesso grafo di Petersen è G(5,2) o {5}+{5/2}.

Esempi

Tra i grafi di Petersen generalizzati ci sono l'n-prisma G(n,1), il grafo di Dürer G(6,2), il grafo di Möbius-Kantor G(8,3), il dodecaedro G(10,2), il grafo di Desargues G(10,3) e il grafo di Nauru G(12,5).

Quattro grafi di Petersen generalizzati – il 3-prisma, il 5-prisma, il grafo di Dürer e G(7,2) – sono tra i sette grafi che sono cubici, 3-connessi sui vertici e ben coperti (che significa che tutti i loro insiemi indipendenti massimi hanno uguale dimensione).^[4]

Proprietà

Questa famiglia di grafi possiede numerose proprietà interessanti. Ad esempio,

G(n,k) è transitivo sui vertici (significa che ha simmetrie che portano qualsiasi vertice a qualsiasi altro vertice) se e solo se n = 10 e k =2 o se k² ≡ ±1 (mod n).
È transitivo sugli spigoli (avendo simmetrie che portano qualsiasi spigolo a qualsiasi altro spigolo) solo nei seguenti altri sette casi: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).^[5] Questi sette grafi sono perciò i soli grafi di Petersen generalizzati simmetrici.
È bipartito se e solo se n è pari e k è dispari.
È un grafo di Cayley se e solo se k² ≡ 1 (mod n).
È ipohamiltoniano quando n è congruente a 5 modulo 6 e k è 2, n−2, (n+1)/2, o (n−1)/2 (tutti e quattro queste scelte di k conducono a grafi isomorfici). È non hamiltoniano anche quando n è divisibile per quattro, almeno uguale a 8, e k è n/2. In tutti gli altri casi, esso ha un ciclo hamiltoniano.^[6] Quando n è congruente a 3 modulo 6 e k is 2, G(n,k) ha esattamente tre cicli hamiltoniani.^[7] Per G(n,2), il numero dei cicli hamiltoniani può essere calcolato mediante una formula che dipende dalla classe di confluenza di n modulo 6 e implica i numeri di Fibonacci.^[8]

Lo stesso grafo di Petersen è l'unico grafo di Petersen generalizzato che non sia 3-colorabile sugli spigoli.^[9] Il grafo di Petersen generalizzato G(9,2) è uno dei pochi grafi conosciuti ad avere to have soltanto un'unica 3-colorazione degli spigoli.^[10]

Ogni grafo di Petersen generalizzato è un grafo a distanza unitaria.^[11]

Note

^ H. S. M. Coxeter, Self-dual configurations and regular graphs, in Bulletin of the American Mathematical Society, vol. 56, 1950, 413–455, DOI:10.1090/S0002-9904-1950-09407-5.
^ Mark E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, in Journal of Combinatorial Theory, vol. 6, 1969, 152–164, DOI:10.1016/S0021-9800(69)80116-X.
^ Jonathan L. Gross e Thomas W. Tucker, Topological Graph Theory, New York, Wiley, 1987. Esempio 2.1.2, p. 58.
^ S. R. Campbell, M. N. Ellingham e Gordon F. Royle, A characterisation of well-covered cubic graphs, in Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 13, 1993, 193–212, MR 1220613.
^ R. Frucht, J. E. Graver e M. E. Watkins, The groups of the generalized Petersen graphs, in Proceedings of the Cambridge Philosophical Society, vol. 70, 1971, 211–218, DOI:10.1017/S0305004100049811.
^ B. R. Alspach, The classification of Hamiltonian generalized Petersen graphs, in Journal of Combinatorial Theory, Series B, vol. 34, 1983, 293–312, DOI:10.1016/0095-8956(83)90042-4, MR 0714452.
^ Andrew Thomason, Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable, in Journal of Graph Theory, vol. 6, n. 2, 1982, 219–221, DOI:10.1002/jgt.3190060218.
^ Allen J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, in Journal of Combinatorial Theory, Series B, vol. 47, n. 1, 1989, 53–59, DOI:10.1016/0095-8956(89)90064-6, MR 1007713.
^ Frank Castagna e Geert Prins, Every Generalized Petersen Graph has a Tait Coloring, in Pacific Journal of Mathematics, vol. 40, 1972.
^ Béla Bollobás, Extremal Graph Theory, Dover, 2004, p. 233. Ristampa dell'edizione del 1978 dell'Academic Press.
^ Arjana Žitnik, Boris Horvat e Tomaž Pisanski, All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, vol. 1109, 2010.