Previous |  Up |  Next


graphs; distance; deformations
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.
[1] V. Baláž J. Koča V. Kvasnička M. Sekanina: A measure for graphs. Časopis Pěst. Mat. 111 (1986), 431-433. MR 0871718
[2] G. Chartrand L. Lesniak: Graphs & Digraphs. (Second Edition), Wadsworth, Monterey (1986). MR 0834583
[3] G. Chartrand F. Saba H. Zou: Edge rotations and distance between graphs. Časopis Pěst. Mat. 110 (1985), 87-91. MR 0791281
[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 0812683
[5] M. Johnson: An ordering of some metrics defined on the space of graphs. Czechoslovak Math. J. 37 (1987), 75-85. MR 0875130 | Zbl 0641.05027
[6] B. Zelinka: On a certain distance between isomorphism classes of graphs. Časopis Pěst. Mat. 100 (1975), 371-373. MR 0416995 | Zbl 0312.05121
[7] B. Zelinka: A distance between isomorphism classes of trees. Czechoslovak Math. J. 33 (1983), 126-130. MR 0687425 | Zbl 0523.05028
[8] B. Zelinka: Comparison of various distances between isomorphism classes of giaphs. Časopis Pěst. Mat. 110 (1985), 289-293. MR 0808079
Partner of
EuDML logo