Il primo snark di Blanuša
| Il primo snark di Blanuša | |
|
Rappresentazione del primo snark di Blanuša | |
| Numero di vertici | 18 |
|---|---|
| Numero di bordi | 27 |
| Distribuzione dei diplomi | 3- regolare |
| Ray | 4 |
| Diametro | 4 |
| Maglia | 5 |
| Automorfismi | 8 (D 4 ) |
| Numero cromatico | 3 |
| Indice cromatico | 4 |
| Proprietà |
Snark normale ipohamiltoniano cubico |
Il blanuša snarks è, in teoria dei grafi, un grafo regolare -3 con 18 vertici e 27 archi.
Proprietà
Proprietà generali
Il diametro del primo snark di Blanuša, la massima eccentricità dei suoi vertici, è 4, il suo raggio , l'eccentricità minima dei suoi vertici, è 4 e la sua maglia , la lunghezza del suo ciclo più breve , è 5. S 'è un 3- grafo connesso a vertici e grafo connesso a 3 spigoli , cioè è connesso e per renderlo disconnesso deve essere privato di almeno 3 vertici o di 3 archi.
Colorazione
Il numero cromatico del primo snark di Blanuša è 3. Cioè, è possibile colorarlo con 3 colori in modo che due vertici collegati da un bordo siano sempre colori diversi. Questo numero è minimo.
L' indice cromatico del primo snark di Blanuša è 4. Vi è quindi una 4-colorazione dei bordi del grafo in modo tale che due bordi incidenti allo stesso vertice siano sempre di colori diversi. Questo numero è minimo. Il primo snark di Blanuša è quindi uno snark , un grafo connesso, senza istmo, cubico, di maglia almeno 5 e di indice cromatico 4. Dal 1898 al 1946, il grafo Petersen è l'unico snark conosciuto, fino a quando Danilo Blanuša ne esibisce due altri esempi, il primo snark di Blanuša e il secondo snark di Blanuša .
Il teorema dello snark , un risultato congetturato da WT Tutte e dimostrato nel 2001 da Robertson, Sanders, Seymour e Thomas, afferma che qualsiasi snark ammette il grafo di Petersen come minore . Il primo snark di Blanuša ammette quindi il grafo di Petersen come minore.
Proprietà algebriche
Il gruppo automorfismo del primo snark di Blanuša è un gruppo di ordine 8 isomorfo al gruppo diedro D 4 , il gruppo di isometrie piane che mantengono un quadrato . Questo gruppo è composto da 4 elementi corrispondenti a rotazioni e altri 4 corrispondenti a riflessioni .
Il polinomio caratteristico della matrice di adiacenza di snuali Blanusa è: .
Blanuša snark generalizzato
Esiste una generalizzazione del primo e del secondo snark di Blanuša in due infinite famiglie di snark di ordine 8 n +10. Sono indicati rispettivamente e . Gli snark Blanuša sono i due membri più piccoli di queste infinite famiglie.
Vedi anche
Collegamenti interni
link esterno
- (en) Eric W. Weisstein , Blanuša Snarks ( MathWorld )
Riferimenti
- (in) Danilo Blanusa , " Problem četiriju boja " , Glasnik Mat. Fiz. Astr. Ser II , vol. 1,1946, p. 31–42
- (in) Ed, Jr. Pegg , Book Review: The Colossal Book of Mathematics , vol. 49,2002( leggi in linea ) , cap. 9, p. 1084–1086.
- (in) Read, RC e Wilson, RJ An Atlas of Graphs. Oxford, Inghilterra: Oxford University Press, pagg. 276 e 280, 1998.