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

Baláž, Vladimír; Kvasnička, Vladimír; Pospíchal, Jiří

Čas. Pěstování Mat. 114, No. 2, 155-159 (1989).

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

MSC:

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

Keywords:

modelling of organic chemistry; distance between finite graphs; common subgraph; supergraph; metrics