Dual approach to edge distance between graphs (Q4732497)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4118413
Language Label Description Also known as
default for all languages
No label defined
    English
    Dual approach to edge distance between graphs
    scientific article; zbMATH DE number 4118413

      Statements

      0 references
      0 references
      0 references
      1989
      0 references
      modelling of organic chemistry
      0 references
      distance between finite graphs
      0 references
      common subgraph
      0 references
      supergraph
      0 references
      metrics
      0 references
      Dual approach to edge distance between graphs (English)
      0 references
      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)\).
      0 references

      Identifiers