Geodesic
On distances between isomorphism classes of graphs
Mathematica Bohemica, Tome 116 (1991) no. 2, pp. 160-169

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.
In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.
DOI : 10.21136/MB.1991.126142
Classification : 05C05, 05C99
Keywords: graphs; distance; deformations 
Benadé, Gerhard; Goddard, Wayne; McKee, Terry A.; Winter, Paul A. On distances between isomorphism classes of graphs. Mathematica Bohemica, Tome 116 (1991) no. 2, pp. 160-169. doi: 10.21136/MB.1991.126142
@article{10_21136_MB_1991_126142,
     author = {Benad\'e, Gerhard and Goddard, Wayne and McKee, Terry A. and Winter, Paul A.},
     title = {On distances between isomorphism classes of graphs},
     journal = {Mathematica Bohemica},
     pages = {160--169},
     year = {1991},
     volume = {116},
     number = {2},
     doi = {10.21136/MB.1991.126142},
     mrnumber = {1112000},
     zbl = {0753.05067},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.1991.126142/}
}
TY  - JOUR
AU  - Benadé, Gerhard
AU  - Goddard, Wayne
AU  - McKee, Terry A.
AU  - Winter, Paul A.
TI  - On distances between isomorphism classes of graphs
JO  - Mathematica Bohemica
PY  - 1991
SP  - 160
EP  - 169
VL  - 116
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.1991.126142/
DO  - 10.21136/MB.1991.126142
LA  - en
ID  - 10_21136_MB_1991_126142
ER  - 
%0 Journal Article
%A Benadé, Gerhard
%A Goddard, Wayne
%A McKee, Terry A.
%A Winter, Paul A.
%T On distances between isomorphism classes of graphs
%J Mathematica Bohemica
%D 1991
%P 160-169
%V 116
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.1991.126142/
%R 10.21136/MB.1991.126142
%G en
%F 10_21136_MB_1991_126142

[1] V. Baláž J. Koča V. Kvasnička M. Sekanina: A measure for graphs. Časopis Pěst. Mat. 111 (1986), 431-433. | MR

[2] G. Chartrand L. Lesniak: Graphs & Digraphs. (Second Edition), Wadsworth, Monterey (1986). | MR

[3] G. Chartrand F. Saba H. Zou: Edge rotations and distance between graphs. Časopis Pěst. Mat. 110 (1985), 87-91. | MR

[4] M. Johnson: Relating metrics, lines and variables defined on graphs to problems in medicinal chemistry. In: Graph Theoгy with Applications to Algorithms & Computer Science, (Y. Alavi et al. eds), Wiley, New York, 1985, 457-470. | MR

[5] M. Johnson: An ordering of some metrics defined on the space of graphs. Czechoslovak Math. J. 37 (1987), 75-85. | MR | Zbl

[6] B. Zelinka: On a certain distance between isomorphism classes of graphs. Časopis Pěst. Mat. 100 (1975), 371-373. | MR | Zbl

[7] B. Zelinka: A distance between isomorphism classes of trees. Czechoslovak Math. J. 33 (1983), 126-130. | MR | Zbl

[8] B. Zelinka: Comparison of various distances between isomorphism classes of giaphs. Časopis Pěst. Mat. 110 (1985), 289-293. | MR

Cité par Sources :