Grafo di Heawood
Nel campo matematico della teoria dei grafi, il grafo di Heawood è un grafo non orientato con 14 vertici e 21 spigoli, che prende nome da Percy John Heawood.[1]
Proprietà combinatorie[modifica | modifica wikitesto]
Il grafo di Heawood è cubico (ossia tutti i suoi vertici hanno grado 3) e tutti i cicli nel grafo hanno 6 o più spigoli. Ogni grafo cubico più piccolo ha cicli più brevi, dunque questo grafo è la gabbia 6, il più piccolo grafo cubico di calibro 6. È un grafo transitivo sulla distanza (vedi il censimento di Foster) e perciò regolare sulla distanza.[2]
Ci sono 24 matching perfetti nel grafo di Heawood; per ogni matching, l'insieme degli spigoli non nel matching forma un ciclo hamiltoniano. Ad esempio, la figura mostra i vertici di questo grafo posto su un ciclo, con le diagonali interne del ciclo che formano un matching. Suddividendo gli spigoli del ciclo in due matching, possiamo ripartire il grafo di Heawood in tre matching perfetti (cioè, 3-colorare i suoi spigoli) in otto modi diversi.[2] Ogni due matching perfetti, e ogni due cicli hamiltoniani, possono essere trasformati l'uno nell'altro da una simmetria del grafo.[3]
Ci sono 28 cicli con sei vertici nel grafo di Heawood. Ogni ciclo 6 è disgiunto esattamente da altri tre cicli 6; tra questi tre cicli 6, ciascuno è la differenza simmetrica degli altri due. Il grafo con un solo nodo per ciclo 6, ed un solo spigolo per ogni coppia disgiunta di cicli 6, è il grafo di Coxeter.[4]
Proprietà geometriche e topologiche[modifica | modifica wikitesto]
Il grafo di Heawood è un grafo toroidale; cioè può essere immerso senza incroci in un toro. Un'immersione di questo tipo pone i suoi vertici e spigoli nello spazio euclideo tridimensionale come l'insieme dei vertici e degli spigoli di un poliedro non convesso con la topologia di un toro, il poliedro di Szilassi.
Il grafo prende il nome di Percy John Heawood, che nel 1890 provò che in ogni suddivisione del toro in poligoni, le regioni poligonali possono essere colorate al massimo da sette colori.[5][6] Il grafo di Heawood forma una suddivisione del toro con sette regioni mutuamente adiacenti, mostrando che questo legame è stretto.
Il grafo di Heawood è anche il grafo di Levi dal piano di Fano, il grafo che rappresenta le incidenze tra i punti e le linee in quella geometria. Con questa interpretazione, i cicli 6 nel grafo di Heawood corrispondono ai triangoli del piano di Fano.
Il grafo di Heawood ha il numero di incroci 3, e questo è il più piccolo grafo cubico con quel numero di incroci[7]. Incluso il grafo di Heawood, ci sono 8 distinti grafi di ordine 14 con numero di incroci 3.
Il grafo di Heawood è un grafo a distanza unitaria: può essere immerso nel piano in modo tale che i vertici adiacenti sono esattamente a distanza di uno, senza due vertici immersi nello stesso punto e nessun vertice immerso in un punto all'interno di uno spigolo. Tuttavia le immersioni conosciute di questo tipo mancano di una qualsiasi delle simmetrie che sono intrinseche nel grafo.[8]
Proprietà algebriche[modifica | modifica wikitesto]
Il gruppo di automorfismo del grafo di Heawood è isomorfico rispetto al gruppo lineare proiettivo PGL2(7), un gruppo di ordine 336.[9] Esso, agisce transitivamente sui vertici, sugli spigoli e sugli archi del grafo. Perciò il grafo di Heawood è un grafo simmetrico. Esso ha automorfismi che portano un qualsiasi vertice a un qualsiasi altro vertice e un qualsiasi spigolo a un qualsiasi altro spigolo. Secondo il censimento di Foster, il grafo di Heawood, citato come F014A, è l'unico grafo simmetrico cubico su 14 vertici.[10][11]
Il polinomio caratteristico del grafo di Heawood è . È l'unico grafo con questo polinomio caratteristico, che lo rende un grado determinato dal suo spettro.
Galleria d'immagini[modifica | modifica wikitesto]
-
-
Il grafo di Heawood ha numero di incroci 3. -
L'indice cromatico del grafo di Heawood è 3. -
Il numero cromatico del grafo di Heawood è 2. -
Un'immersione del grafo di Heawood in un toro (mostrata come un quadrato con condizioni periodiche al contorno) che lo ripartisce in sette regioni mutuamente adiacenti.
Note[modifica | modifica wikitesto]
- ^ MathWorld
- ^ a b Brouwer, Andries E., Heawood graph, in Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).
- ^ Abreu M., Aldred R. E. L., Funk M., Jackson Bill, Labbate D., Sheehan J., Graphs and digraphs with all 2-factors isomorphic, in Journal of Combinatorial Theory, Serie B, vol. 92, n. 2, 2004, 395-404, DOI:10.1016/j.jctb.2004.09.004, MR 2099150..
- ^ Dejter, Italo J., From the Coxeter graph to the Klein graph, in Journal of Graph Theory, 2011, DOI:10.1002/jgt.2059. arXiv 1002.1960.
- ^ Brown, Ezra, The many names of (7,3,1) (PDF), in Mathematics Magazine, vol. 75, n. 2, 2002, pp. pp. 83-94, DOI:10.2307/3219140. URL consultato il 24 febbraio 2013 (archiviato dall'url originale il 5 febbraio 2012). JSTOR 3219140.
- ^ Heawood, P. J., Map colouring theorems, in Quarterly J. Math. Oxford Ser., vol. 24, 1890, pp. pp. 322-339.
- ^ (EN) Sequenza A110507, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
- ^ Gerbracht, Eberhard H.-A., Eleven unit distance embeddings of the Heawood graph, 2009. arXiv (EN) Eberhard H.-A. Gerbracht, Eleven Unit Distance Embeddings of the Heawood Graph, su Università Cornell. URL consultato l'8 dicembre 2021 (archiviato il 7 maggio 2021).
- ^ Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, New York, North Holland, 1976, p. p. 237, ISBN 0-444-19451-7 (archiviato dall'url originale il 13 aprile 2010).
- ^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archiviato il 20 luglio 2008 in Internet Archive.
- ^ Conder, M. e Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Grafo di Heawood
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Eric W. Weisstein, Grafo di Heawood, su MathWorld, Wolfram Research.
