Geodesic
Combinatorial graph complexity
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.

Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica

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. 
@article{RLINA_1975_8_59_6_a8,
     author = {Minoli, Daniel},
     title = {Combinatorial graph complexity},
     journal = {Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali},
     pages = {651--661},
     publisher = {mathdoc},
     volume = {Ser. 8, 59},
     number = {6},
     year = {1975},
     zbl = {0361.05046},
     mrnumber = {0476578},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RLINA_1975_8_59_6_a8/}
}
TY  - JOUR
AU  - Minoli, Daniel
TI  - Combinatorial graph complexity
JO  - Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
PY  - 1975
SP  - 651
EP  - 661
VL  - 59
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/RLINA_1975_8_59_6_a8/
LA  - en
ID  - RLINA_1975_8_59_6_a8
ER  - 
%0 Journal Article
%A Minoli, Daniel
%T Combinatorial graph complexity
%J Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
%D 1975
%P 651-661
%V 59
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/RLINA_1975_8_59_6_a8/
%G en
%F RLINA_1975_8_59_6_a8
Minoli, Daniel. Combinatorial graph complexity. 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. http://geodesic.mathdoc.fr/item/RLINA_1975_8_59_6_a8/

[1] C. W. Marshall (1971) - Applied Graph Theory, Wiley-Interscience, New York. | MR | Zbl

[2] A. Mowshowitz (1968) - Entropy and the Complexity of Graphs. II, «Bull. Math. Biophys.», 30, 225-240. | DOI | MR | Zbl

[3] E. Trucco (1956) - A Note on the Information Content of Graphs, «Bull. Math. Biophys.», 129-135. | DOI | MR

[4] D. Minoli - Graph Complexity, Unpublished Thesis.