Il grafico di Doyle
| Il grafico di Doyle | |
|
Rappresentazione del grafico di Doyle | |
| Numero di vertici | 27 |
|---|---|
| Numero di bordi | 54 |
| Distribuzione dei diplomi | 4- regolare |
| Ray | 3 |
| Diametro | 3 |
| Maglia | 5 |
| Automorfismi | 54 |
| Numero cromatico | 3 |
| Indice cromatico | 5 |
| Proprietà |
Regolare Hamiltoniano Euleriano Cayley Peak-transitivo Ridge-transitivo |
Il grafo di Doyle (o grafo di Holt ) è, in teoria dei grafi , un grafo quadridimensionale con 27 vertici e 54 archi. Questo è l'esempio grafico più piccolo di un grafico essendo vertice-transitivo e edge-transitivo ma non simmetrica . Tali grafici sono rari. Deve il suo nome a Peter G. Doyle e Derek F. Holt che lo scoprirono entrambi in modo indipendente rispettivamente nel 1976 e nel 1981.
Proprietà
Proprietà generali
Il diametro del grafo di Doyle, l'eccentricità massima dei suoi vertici, è 3, il suo raggio , l'eccentricità minima dei suoi vertici, è 3 e la sua maglia , la lunghezza del suo ciclo più breve , è 5. Questo è di un vertice 4 -grafo connesso e di un grafo a 4 spigoli , cioè è connesso e che per renderlo disconnesso deve essere privato di almeno 4 vertici o 4 archi.
È anche un grafico hamiltoniano con 98.472 cicli hamiltoniani distinti.
Colorazione
Il numero cromatico del grafo di Doyle è 3. Vale a dire, è possibile colorarlo con 3 colori in modo che due vertici collegati da un bordo siano sempre colori diversi ma questo numero è minimo. Non esiste una 2 colorazione valida del grafico.
L' indice cromatico del grafo di Doyle è 5. Vi è quindi una 5-colorazione degli spigoli del grafo in modo tale che due spigoli incidenti allo stesso vertice siano sempre di colore diverso. Questo numero è minimo.
Proprietà algebriche
Il gruppo di automorfismi del grafo di Doyle è un gruppo di ordine 54.
Il polinomio caratteristico della matrice di adiacenza del grafo è Doyle: .
Vedi anche
Collegamenti interni
link esterno
- (en) Eric W. Weisstein , Doyle Graph ( MathWorld )
Riferimenti
- Doyle, P. "Un grafico a 27 vertici che è transitivo ai vertici e transitivo ai margini ma non transitivo a L". Ottobre 1998. [1]
- (in) Brian Alspach , Dragan Marušič e Lewis Nowitz , " Constructing Graphs qui are ½-Transitive " , Journal of the Australian Mathematical Society (Serie A) , vol. 56, n o 3,1994, p. 391–402 ( DOI 10.1017 / S1446788700035564 , leggi in linea ).
- Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory , CRC Press, 2004, ( ISBN 1-58488-090-2 ) , p. 491.
- PG Doyle On Transitive Graphs , Senior Thesis, 1976, Harvard College.
- (in) Derek F. Holt , " A graph qui est edge transitive but not transitive arc " , Journal of Graph Theory , vol. 5, n o 2diciannove ottantuno, p. 201–204 ( DOI 10.1002 / jgt.3190050210 ).