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.[1] Se il grafo non contiene alcun ciclo (è cioè un grafo aciclico), il suo calibro si definisce infinito.[2] 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 ${\displaystyle g}$ – cioè più piccolo possibile – è noto come una gabbia ${\displaystyle g}$ o come una gabbia (3,${\displaystyle 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.[3] 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 ${\displaystyle g}$ e ${\displaystyle \chi }$, esiste un grafo con un calibro almeno di ${\displaystyle g}$ e un numero cromatico almeno di ${\displaystyle \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.[4] Più precisamente, dimostrò che un grafo aleatorio su ${\displaystyle n}$ vertici, formato scegliendo indipendentemente se includere ogni bordo con probabilità ${\displaystyle n^{(1-g)/g}}$, ha, con probabilità che tende a 1 quando ${\displaystyle n}$ va a infinito, al massimo ${\displaystyle n/2}$ cicli di lunghezza ${\displaystyle g}$ o minore, ma non ha alcun insieme indipendente di dimensione ${\displaystyle n/2k}$. Perciò, eliminare un vertice da ogni ciclo corto lascia un grafo più piccolo con calibro maggiore di ${\displaystyle g}$, in cui ogni classe di colore di una colorazione deve essere piccola e che quindi richiede almeno ${\displaystyle 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.

Note

1. R. Diestel, Graph Theory, p. 8. 3ª edizione, Springer-Verlag, 2005
2. Girth -- Wolfram MathWorld.
3. Andries E. Brouwer, Cages. Supplemento elettronico al libro Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
4. Paul Erdős, Graph theory and probability, in Canadian Journal of Mathematics, vol. 11, 1959, 34-38, DOI:10.4153/CJM-1959-003-9..

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.