Grafo di Petersen generalizzato
# 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 e a questi grafi nel 1969 fu dato il loro nome da Mark Watkins.

## Definizione e notazione

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

    ${u_0,$ $u_1,$ ..., $u_{n−1},$ $v_0,$ $v_1,$ ..., $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.

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

## 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^2$ ≡ ±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). 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^2$ ≡ 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. Quando n è congruente a 3 modulo 6 e k is 2, G(n,k) ha esattamente tre cicli hamiltoniani. 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.

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

Ogni grafo di Petersen generalizzato è un grafo a distanza unitaria.

