Combinatorial graph complexity

Minoli, Daniel

Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali, Série 8, Tome 59 (1975) no. 6, pp. 651-661

Résumé

Qui si ottiene una misura della complessità di un grafo non orientato; varie misure sono già state proposte, ma esse non soddisfano ad alcune proprietà fondamentali che una siffatta funzione dovrebbe avere, date essenzialmente dal carattere monotonico della complessità rispetto al numero dei vertici, dei lati, e del grado di connessione del grafo. Ecco la nostra definizione: Un cammino tra due vertici $v_{i}$ and $v_{j}$, $v_{i} \ne v_{j}$, dicesi proprio se 1) contiene $v_{i}$ e $v_{j}$ esattamente una volta, rispettivamente come vertice inziale e finale, e 2) contiene ogni particolare lato al massimo una volta; la complessità $\chi(G)$ di un grafo $G$ viene quindi così definita: $$\chi(G) = \frac{ne}{n+e} \,\, \sum_{(v_{i},v_{j}),i} \, \sigma_{ij},$$ dove $e$ = numero dei lati, $n$ = numero dei vertici, $\sigma_{ij}$ = numero dei cammini propri tra i vertici $v_{i}$ e $v_{j}$. Proprietà di questa complessità vengon qui investigate.