Grafi non cordali



Grafo di Tutte

Il grafo di Tutte T è il più piccolo grafo non cordale con sette nodi a radici intere: 0, 1, 2, 3, 3, 3, 4.

Calcoliamo il polinomio cromatico di T

Il grafo di Tutte può essere schematizzato nel seguente modo:




P(T,t) = P(T-e)-P(T\e) = [ P(K5) · P(K5) · P(K2)] P(K1) -1 - P(T\e)
P(K4)
= [ (t)5 · (t)5 · (t)2] (t)1 -1 - (t)6
(t)4
= (t)5 · [(t)5 · (t)4 -1 · (t)2 · (t)1 -1 - (t - 5) ]
= (t)5 · [(t - 4) · (t - 1) - (t - 5) ]
= (t)5 · (t 2 - 6t + 9)
= (t)5 · (t - 3) 3


Il grafo di Tutte è il solo grafo non cordale con sette nodi a radici intere.

Se cerchiamo altri grafi non cordali a radici intere (o reali) bisogna cercare fra i grafi con otto nodi: partiamo allora dal grafo di Tutte e vi aggiungiamo un nodo.

I 13 grafi connessi non cordali a radici reali

(con otto nodi)


Radici: 0, 1, 2, 3, 3, 3, 4 + 1



Radici: 0, 1, 2, 3, 3, 3, 4 + 1



Radici: 0, 1, 2, 3, 3, 3, 4 + 1



Radici: 0, 1, 2, 3, 3, 3, 4 + 2



Radici: 0, 1, 2, 3, 3, 3, 4 + 2



Radici: 0, 1, 2, 3, 3, 3, 4 + 2



Radici: 0, 1, 2, 3, 3, 3, 4 + 3



Radici: 0, 1, 2, 3, 3, 3, 4 + 3



Radici: 0, 1, 2, 3, 3, 3, 4 + 4



Radici: 0, 1, 2, 3, 3, 3, 4 + 4



Radici: 0, 1, 2, 3, 3, 3, 4 + 5



Radici: 0, 1, 2, 3, 4, 4, 4, 5
(espansione cromatica del grafo di Tutte)

In questo grafo la trasformazione usata non è elementare: non abbiamo collegato il nuovo nodo ad una cricca e non abbiamo neanche fatto un'espansione cromatica. Il suo polinomio cromatico è:
(t)6 · (t 2 - 7t + 11)
(a radici reali)
Inoltre è il più piccolo grafo non cordale ad otto nodi a radici irrazionali.

Il calcolo di questo polinomio è stato fatto utilizzando la generalizzazione della costruzione di Tutte.

Generalizzazione della costruzione di Tutte

A e B sono due cricche di ordine rispettivamente a e b.
(Con a=4 e b=1 si ha il grafo di Tutte.)
Calcoliamo il polinomio cromatico di questo grafo, che chiamiamo Ma,b

Siano rispettivamente A' e B' i grafi A e B a cui sono stati aggiunti i nodi c e d; in tal modo A' e B' diventano due cricche rispettivamente di ordine a+2 e b+2.

Sia e l'arco, non esistente nel grafo Ma,b, che collega i nodi c e d.

Poiché:

P(Ma,b+e) = P(Ma,b) - P(Ma,b+e \ e) (decomposizione degli archi)

Allora:

P(Ma,b) = P(Ma,b+e) + P(Ma,b+e \ e)

= P(A') · P(B') + P(Ma,b+e\e)
P(K2)
= (t)a+2 · (t)b+2 · (t)2 -1 + (t)a+1 · (t)b+1 · (t)1 -1
= (t)a+1 · (t)b+1 · (t)2 -1 [ (t-a-1) · (t-b-1) + (t-1) ]
= (t)a+1 · (t)b+1 · (t)2 -1 [ t 2 - (a+b+1) t + ab + a + b ]
= (t)a+1 · (t)b+1 · (t)2 -1 ma,b(t)

Studio di ma,b(t)

ma,b(t) = [ t² - (a+b+1) t + ab + a + b ]

= (a + b + 1)² - 4 (a + b + ab)

a=b:

= 1 - 4a

A parte il caso a = b = 0 in cui si ha P(M0,0) = t², non ha radici reali.

ab:

Sia b > a: b = a+h, h > 0

= h² - 2h + 1 - 4a

Calcoliamo il discriminante di :

h = 16 a , quindi > 0 per h > 1 + 2 e h < 1 - 2 (quest'ultima soluzione non è accettata poiché deve essere b > a)

Quindi si hanno radici reali per a + 1 + 2 b

Nota

Per a = 1 e b = 4 si ha: T = M1,4
(dove T è il grafo di Tutte)

Generalizzazione della costruzione a piramide

Piramide

Chiamiamo H il grafo costituito dal grafo G al quale è stato aggiunto un nodo v collegandolo ad una cricca di ordine m.
Si ha:

p(H,t) = (t-m) p(G,t) (vedi TDF)

Vediamone alcune generalizzazioni:

1) Bi-Piramide

Modifichiamo la piramide aggiungendo al grafo G non più un solo nodo ma due (x e y), collegando il nodo x a b nodi della cricca di ordine m, e il nodo y ai restanti a nodi della cricca
Chiamo Ba,b tale costruzione.

Si ha:

p(Ba,b;t) = p(G,t) · [ t² - (a+b+1) t + ab + a + b ] = p(G,t) · ma,b(t)



2) Bi-Piramide estesa

Modifichiamo la bi-piramide in modo tale che i nodi x e y siano collegati ad r nodi della cricca di ordine m: in altre parole l'intersezione tra l'insieme degli a nodi collegati ad y e quello dei b nodi collegati ad x non è più nulla.

Chiamo Ba,b;r tale costruzione.

Si ha:

p(Ba,b;r;t) = p(G,t) · [ t² - (a+b+1) t + ab + a + b - r ]



3) Tri-Piramide

Modifichiamo la piramide aggiungendo al grafo G non più un solo nodo ma tre (x, y, z), collegando il nodo x ad a nodi della cricca di ordine m, il nodo y a b nodi della cricca, e z a c nodi della cricca; l'insieme degli a nodi collegati a x e l'insieme dei b nodi collegati ad y hanno in comune r1 nodi; l'insieme dei c nodi collegati a z e l'insieme dei b nodi collegati ad y hanno in comune r2 nodi.
Chiamo Ba,b,c;r1,r2 tale costruzione.

Si ha:

p(Ba,b,c;r1,r2;t) = p(G,t) · q(t).

dove q(t) è un polinomio in t di terzo grado; se tale polinomio ha radici intere, abbiamo un esempio di grafo non cordale a radici intere contenente un C5 senza corde.


Nota

Come si è visto il grafo di Tutte (avente 7 nodi) è un esempio di grafo non cordale a radici intere contenente un C4. Abbiamo anche visto che aggiungendo un nodo in vari modi al grafo di Tutte si ottengono 13 grafi non cordali connessi a radici intere e reali contenenti ancora un C4.
Il che vuole dire che se cerchiamo grafi non cordali a radici intere contenenti un C5, dobbiamo cercarli fra quelli aventi un numero di nodi superiore ad otto.
Quest'ultima generalizzazione potrebbe allora essere utile in questa ricerca.


Torna all'indice