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]

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

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]

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

1. 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).
2. È 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.
3. È bipartito se e solo se n è pari e k è dispari.
4. È un grafo di Cayley se e solo se k² ≡ 1 (mod n).
5. È 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]

• Grafo di Petersen

• Wikimedia Commons contiene immagini o altri file su Grafo di Petersen generalizzato

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica