Si dicono “tornei” i grafi completi orientati, perché corrispondono a schemi di gironi semplici all’italiana, nei quali ogni squadra (corrispondente a un nodo) incontra tutte le altre, immaginando la direzione come una freccia che va dalla squadra di casa a quella ospite (senza il requisito che una squadra gichi tante volte in casa quante fuori).
La congettura avanzata nel 1995 da Nathaniel Dean è il caso della congettura del secondo vicinato limitata ai tornei. Nei termini dei tornei si può enunciare dicendo che in ogni girone all’italiana semplice esiste almeno una squadra s tale che l’insieme degli avversari incontrati in casa dalle squadre contro le quali s ha giocato in casa contiene almeno tante squadre quante quelle contro le quali s ha giocato in casa.
Il quadrato di un grafo è il grafo ottenuto congiungendo ogni nodo a tutti quelli a distanza 1 o due da esso, ovvero aggiungendo archi tra tutte le coppie di nodi distinti connesse tramite due archi.
Nel caso di grafi orientati, vuol dire aggiungere a ogni nodo un arco che lo congiunge ai nodi raggiungibili da esso percorrendo esattamente due archi.
La congettura di Dean può quindi essere espressa come segue: facendo il quadrato di ogni torneo, esiste almeno un nodo il cui vicinato raddoppia almeno di numero.
Nathaniel Dean e Brenda J. Latka dimostrarono nel 1995 che la congettura è vera:
-
per i grafi nei quali esiste almeno un nodo dal quale escono al massimo 5 archi;
-
per i grafi nei quali per qualsiasi coppia di nodi la differenza tra il numero di archi uscenti è al massimo uno.
La congettura di Dean fu dimostrata da David C. Fischer nel 1996.