Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo.R. Diestel, Graph Theory, p. 8. 3ª edizione, Springer-Verlag, 2005 Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito. Ad esempio, un ciclo di ordine 4 (quadrato) ha calibro 4. Anche una griglia ha calibro 4, e una maglia triangolare ha calibro 3. Un grafo con calibro pari a 4 o superiore è senza triangoli.
Gabbie Un grafo cubico (tutti i vertici hanno grado 3) di calibro – cioè più piccolo possibile – è noto come una gabbia o come una gabbia (3,). Il grafo di Petersen è l'unica gabbia 5 (è il più piccolo grafo cubico di calibro 5), il grafo di Heawood è l'unica gabbia 6, il grafo di McGee è l'unica gabbia 7 e il grafo di Tutte-Coxeter è l'unica gabbia 8. Supplemento elettronico al libro Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag). Possono esistere gabbie multiple per un dato calibro. Per esempio ci sono tre gabbie 10 non isomorfiche, ognuna con 70 vertici: la gabbia 10 di Balaban, il grafo di Harries e il grafo di Harries-Wong.
Calibro e colorazione dei grafi Per un qualsiasi intero positivo e , esiste un grafo con un calibro almeno di e un numero cromatico almeno di ; ad esempio, il grafo di Grötzsch è senza triangoli e ha numero cromatico 4, e ripetendo la costruzione di Jan Mycielski usata per formare il grado di Grötzsch produce grafi senza triangoli con numero cromatico arbitrariamente grande. Paul Erdős fu il primo a provare il risultato generale, usando il metodo probabilistico.. Più precisamente, dimostrò che un grafo aleatorio su vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità , ha, con probabilità che tende a 1 quando va a infinito, al massimo cicli di lunghezza o minore, ma non ha alcun insieme indipendente di dimensione . Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di , in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno colori in una qualsiasi colorazione.
Concetti correlati Il calibro dispari e il calibro pari di un grafo sono le lunghezze rispettivamente del più breve ciclo dispari e del più breve ciclo pari.
Pensato come la minore lunghezza di un ciclo non banale, il calibro ammette generalizzazioni naturali come sistole 1 o sistoli superiori in geometria sistolica.
Note
Collegamenti esterni
Categoria:Teoria dei grafi