Dual approach to edge distance between graphs. (English) Zbl 0683.05041

For mathematical modelling of organic chemistry, two concepts of distance between finite graphs has been developed. The main result of the paper is that these two concepts are identical.
A common subgraph (supergraph) of two graphs \(G_ 1\) and \(G_ 2\) consists of a subgraph \(G_ 1'\subseteq G_ 1\) (supergraph \(G_ 1'\supseteq G_ 1)\) and a subgraph \(G_ 2'\subseteq G_ 2\) (supergraph \(G_ 2'\supseteq G_ 2)\) such that \(G_ 1'\cong G_ 2'\). A maximal common subgraph (minimal common supergraph) of two graphs \(G_ 1\) and \(G_ 2\) is a common subgraph (supergraph) which contains the largest (smallest) possible number of edges, it is denoted by \(G_ 1\cap G_ 2\) \((G_ 1\cup G_ 2)\). Set \(g(G,H)=| E(G)| -| E(G\cap H)|,\) \(h(G,H)=| E(G\cup H)| -| E(G)|.\) Now the two distances are \[ d(G,H)=g(G,H)+g(H,G)+| | V(G)| -| V(H)| | \quad and\quad D(G,H)=h(G,H)+h(H,G)+| | V(G)| -| V(H)| |. \] The authors prove that D and d are metrics, \(D=d\) and \(d(G,H)=d(\bar G,\bar H)\).
Reviewer: L.A.Székely


05C99 Graph theory
54E35 Metric spaces, metrizability
92Exx Chemistry