Grafo di Heawood

Da Wikipedia, l'enciclopedia libera.
Il 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 sorgente]

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 sorgente]

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 sorgente]

Il gruppo di automorfismo del grafo di Heawood è isomorfico rispetto al gruppo lineare proiettivo PGL2(7), un gruppo di ordine 336.[9] Esso,afisce 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 frafo simmetrico cubico su 14 vertici.[10][11]

Il polinomio caratteristico del grafo di Heawood è (x-3) (x+3) (x^2-2)^6. È l'unico grafo con questo polinomio caratteristico, che lo rende un frado determinato dal suo spettro.

Galleria[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ (EN) Eric W. Weisstein, Grafo di Heawood in MathWorld, Wolfram Research.
  2. ^ a b Brouwer, Andries E., Heawood graph in Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).
  3. ^ 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, pp. 395-404, DOI:10.1016/j.jctb.2004.09.004, MR 2099150..
  4. ^ 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.
  5. ^ Brown, Ezra, The many names of (7,3,1) in Mathematics Magazine, vol. 75, nº 2, 2002, pp. pp. 83-94, DOI:10.2307/3219140. JSTOR 3219140.
  6. ^ Heawood, P. J., Map colouring theorems in Quarterly J. Math. Oxford Ser., vol. 24, 1890, pp. pp. 322-339.
  7. ^ (EN) Sequenza A110507 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  8. ^ Gerbracht, Eberhard H.-A., Eleven unit distance embeddings of the Heawood graph, 2009. arXiv 0912.5395 0912.539.
  9. ^ Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, New York, North Holland, 1976, p. p. 237, ISBN 0-444-19451-7.
  10. ^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
  11. ^ Conder, M. e Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica