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
{u0, u1, ..., un−1, v0, v1, ..., vn−1}
e insieme degli spigoli
{ui ui+1, ui vi, vi vi+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. Esempio 2.1.2, p. 58.
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 k2 ≡ ±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 k2 ≡ 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. Ristampa dell'edizione del 1978 dell'Academic Press.
Ogni grafo di Petersen generalizzato è un grafo a distanza unitaria.
Note
Voci correlate Grafo di Petersen
Altri progetti
Categoria:Grafi regolari