Calibro (teoria dei grafi)

Nella teoria dei grafi, il calibro (in inglese girth) di un grafo è la lunghezza del ciclo più corto contenuto nel grafo. 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 $g$ – cioè più piccolo possibile – è noto come una gabbia $g$ o come una gabbia (3,$g$). 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. 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.

• 
  Il grafo di Petersen ha un calibro di 5
• 
  Il grafo di Heawood ha un calibro di 6
• 
  Il grafo di McGee ha un calibro di 7
• 
  Il grafo di Tutte-Coxeter (gabbia 8 di Tutte) ha un calibro di 8

Calibro e colorazione dei grafi

Per un qualsiasi intero positivo $g$ e $\chi$, esiste un grafo con un calibro almeno di $g$ e un numero cromatico almeno di $\chi$; 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 $n$ vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità $n^{(1-g)/g}$, ha, con probabilità che tende a 1 quando $n$ va a infinito, al massimo $n/2$ cicli di lunghezza $g$ o minore, ma non ha alcun insieme indipendente di dimensione $n/2k$. Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di $g$, in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno $k$ 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.

Collegamenti esterni

• (EN) Computing the girth of a graph (PDF), su webcourse.cs.technion.ac.il, Technion, 31 dicembre 2013. URL consultato il 28 dicembre 2012.