On distances between isomorphism classes of graphs

Gerhard Benadé; Wayne Goddard; Terry A. McKee; Paul A. Winter

Mathematica Bohemica (1991)

  • Volume: 116, Issue: 2, page 160-169
  • ISSN: 0862-7959

Abstract

top
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.

How to cite

top

Benadé, Gerhard, et al. "On distances between isomorphism classes of graphs." Mathematica Bohemica 116.2 (1991): 160-169. <http://eudml.org/doc/29296>.

@article{Benadé1991,
abstract = {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.},
author = {Benadé, Gerhard, Goddard, Wayne, McKee, Terry A., Winter, Paul A.},
journal = {Mathematica Bohemica},
keywords = {graphs; distance; deformations; graph isomorphism; deformations; measure; distance},
language = {eng},
number = {2},
pages = {160-169},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On distances between isomorphism classes of graphs},
url = {http://eudml.org/doc/29296},
volume = {116},
year = {1991},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 116
IS - 2
SP - 160
EP - 169
AB - 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.
LA - eng
KW - graphs; distance; deformations; graph isomorphism; deformations; measure; distance
UR - http://eudml.org/doc/29296
ER -

References

top
  1. V. Baláž J. Koča V. Kvasnička M. Sekanina, A measure for graphs, Časopis Pěst. Mat. 111 (1986), 431-433. (1986) MR0871718
  2. G. Chartrand L. Lesniak, Graphs & Digraphs, (Second Edition), Wadsworth, Monterey (1986). (1986) MR0834583
  3. G. Chartrand F. Saba H. Zou, Edge rotations and distance between graphs, Časopis Pěst. Mat. 110 (1985), 87-91. (1985) MR0791281
  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. (1985) MR0812683
  5. M. Johnson, An ordering of some metrics defined on the space of graphs, Czechoslovak Math. J. 37 (1987), 75-85. (1987) Zbl0641.05027MR0875130
  6. B. Zelinka, On a certain distance between isomorphism classes of graphs, Časopis Pěst. Mat. 100 (1975), 371-373. (1975) Zbl0312.05121MR0416995
  7. B. Zelinka, A distance between isomorphism classes of trees, Czechoslovak Math. J. 33 (1983), 126-130. (1983) Zbl0523.05028MR0687425
  8. B. Zelinka, Comparison of various distances between isomorphism classes of giaphs, Časopis Pěst. Mat. 110 (1985), 289-293. (1985) MR0808079

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.