SALVATORE ANTONUCCI

Costruendo grafi regolari

Pages: 265-270
Received: 29 April 1991
Mathematics Subject Classification: 05C35

Abstract Un grafo regolare di ordine $n$ e di valenza $k$ si dirà ti tipo $R_{n,k}$. Per indicare che il vertice $a$ è adiacente al vertice $b$ scriveremo $a\proptob$; per indicare che $a$ adiacente ad ogni vertice di $S$ scriveremo $a\proptoS$ Inoltre con $\chi(G)$ indicheremo il numero cromatico del grafo $G$ e con $\chi(R_{n,k})$ il numero cromato di un grafo di grafo di tipo $R_{n,k}$. Infine, in tutto l'articolo, quando si parlerà di un "un solo grafo" si intenderà a meno di isomorfismi; talvolta, pure si dirà grafo $R_{n,k}$ in luogo di grafo $G$ di tipo $R_{n,k}$. Lo scopo di questo lavoro è la costruzione, ove possibile la classificazione, lo studio di proprietà (come la forte regolarità) e la colorazione (ma non specificatamente) di grafi regolari. L'operazione del tipo suddetto non è, naturalmente, affrontabile in generale: nemmeno un computer veloce e capace (di memoria) potrebbe effettuare una classificazione dei grafi regolari sottoposti alla sola condizione di essere di ordine $n$ e di valenza $k$, neanche, naturalamente, se fosse supportato da un software sofisticato. Effettueremo l'perazione, perciò, introducendo condizioni supplementari e in maniera un pò "random", non avendo la pretesa, in questa sede, di una sistemazione definitiva della materia. Ciò consentirà di cogliere aspetti vari del problema e, nel contempo, favorirà la scoperta di altrettanti problemi aperti, anche se non saranno pedissequamente elencati.