Grafo di Goldner-Harary
Il Grafo di Goldner-Harary è un grafo non orientato con 11 vertici e 27 spigoli. Prende il nome dai matematici A. Goldner e Frank Harary, i quali nel 1975 dimostrarono che esso era il più piccolo grafo planare massimale di tipo non hamiltoniano.[1][2][3] Lo stesso grafico era già stato indicato come un esempio di poliedro simpliciale non hamiltoniano da Branko Grünbaum nel 1967.[4]
Esso possiede un numero cromatico di 4, un indice cromatico di 8, una circonferenza pari a 3, un raggio di 2, un diametro anch'esso pari a 2 ed è un grafo a 3 bordi. Inoltre, è un albero di lunghezza pari a 3: come ogni k-albero, è anche un grafo cordale e, in quanto grafo di tipo "3-albero" (albero ternario) planare, è un esempio di rete apolloniana.
Proprietà[modifica | modifica wikitesto]
Il grafo Goldner-Harary è di tipo planare poiché può essere tracciato sul piano senza attraversare i suoi bordi. Inoltre, è di tipo planare massimale, poiché tutte le sue facce sono triangolari, se disegnato su un piano. Come ogni grafo planare massimale, è anche k-connesso a 3 vertici (), vale dire che resta un sottografo connesso anche qualora vengano rimossi uno o due dei suo vertici: per diventare sconnesso devono essere rimossi 3 vertici o 3 bordi.
Dato che il numero più piccolo possibile di vertici per un grafico poliedrico non hamiltoniano è 11, il Grafo di Goldner-Harary è un grafo planare massimale col numero minimo di vertici, ma non di spigoli: infatti, il grafo di Herschel è un poliedro non hamiltoniano avente 11 vertici e 18 spigoli, anziché 27.
Quale grafico planare massimale non hamiltoniano, il grafico di Goldner–Harary fornisce un esempio di grafico planare con uno spessore di libro (book thickness) maggiore di due.[5] Sulla base dell'esistenza di tali esempi, Bernhart e Kainen ipotizzarono che lo spessore del libro dei grafici planari potesse essere reso arbitrariamente grande, ma furono smentiti successivamente dalla dimostrazione secondo la quale tutti i grafici planari hanno lo spessore di libro inferiore o uguale a 4.[6]
In particolare, il grafico di Goldner–Harary ha uno spessore di libro pari a 3.
Geometria[modifica | modifica wikitesto]
Secondo il teorema di Steinitz, il grafo di Goldner-Haray è un grafo poliedrico: poiché è planare ed è un albero ternario, esiste un poliedro convesso che può avere il grafico Goldner-Harary come proprio n-scheletro, avente n sottospazi topologici ottenuti in altrettanti passi discreti.
Un poliedro che rappresenta il grafico Goldner-Harary può essere costruito incollando un tetraedro su ciascuna delle tre facce di una piramide triangolare, in modo simile al modo in cui un triacisottaedro è ottenibile incollando un tetraedro su ciascuna faccia di un ottaedro: è il "Kleetopo" di una dipiramide triangolare.[4][7] Il duale del grafo di Goldner-Harary è rappresentato geometricamente da un prisma triangolare troncato.
Colore[modifica | modifica wikitesto]
Il numero cromatico è 4, che è il minimo valore possibile per il quale il grafo può essere colorato in modo tale che qualsiasi coppia di vertici connessi da un bordo siano sempre di colori diversi.
L'indice cromatico del grafico Goldner-Harary è 8, che è il minimo nnumero di colori applicabile ai bordi in modo tale che qualsiasi coppia di bordi incidenti (che insistono) sullo stesso vertice non abbiano mai lo stesso colore.
È possibile contare le diverse colorazioni del grafo di Goldner-Harary. Esso è descritto in rapporto al numero di colori ammessi da una funzione polinomiale associata al polinomio cromatico, che è un polinomio di grado 11, che accettacome poissibili radici tutti gli interi positivi o nulli strettamente miniori di 4. È uguale a: .
Proprietà algebriche[modifica | modifica wikitesto]
Il gruppo di automorfismi del grafo di Goldner-Harary è un gruppo di ordine 12 isomorfo rispetto al gruppo diedrale D6, il gruppo di isometrie nel piano che rendono un esagono regolare. Questo gruppo è composto da 6 elementi corrispondenti alle rotazioni e altri 6 corrispondenti alle riflessioni planari.
Il polinomio caratteristico della matrice delle adiacenze di un grafico Goldner-Harary è il seguente:.
Note[modifica | modifica wikitesto]
- ^ A. Goldner e F. Harary, Note on a smallest nonhamiltonian maximal planar graph, in Bull. Malaysian Math. Soc., vol. 6, n. 1, 1975, pp. 41–42.. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference from elenco delle pubblicazioni di Harary.
- ^ Dillencourt, M. B., Polyhedra of small orders and their Hamiltonian properties, in Journal of Combinatorial Theory, Series B, vol. 66, 1996, pp. 87–122, DOI:10.1006/jctb.1996.0008..
- ^ R. C. Read e R. J. Wilson, An Atlas of Graphs, Oxford, England, Oxford University Press, 1998, p. 285..
- ^ a b Branko Grünbaum, Convex Polytopes, Wiley Interscience, 1967, p. 357.. Graduate Texts in Mathematics 221, Springer-Verlag, 2003, ISBN 978-0-387-40409-7, p. 357, 2ª edizione.
- ^ Frank R. Bernhart e Paul C. Kainen, The book thickness of a graph, in Journal of Combinatorial Theory, Series B, vol. 27, n. 3, 1979, pp. 320–331, DOI:10.1016/0095-8956(79)90021-2.. Cfr. in particolare la figura 9.
- ^ Mihalis Yannakakis, Four pages are necessary and sufficient for planar graphs, in Proc. 18th ACM Symp. Theory of Computing (STOC), 1986, pp. 104–108, DOI:10.1145/12130.12141..
- ^ Günter Ewald, Hamiltonian circuits in simplicial complexes, in Geometriae Dedicata, vol. 2, n. 1, 1973, pp. 115–125, DOI:10.1007/BF00149287..
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su grafo di Goldner-Harary
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Eric W. Weisstein, Goldner-Harary Graph, su MathWorld.
