Planar graphs and greatest common subgraphs

DOI10.1007/BF02988313MaRDI QIDQ687720zbMATH OpenOpenAlexFDO

Publication date 28 October 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02988313

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Review text

A greatest common subgraph of two graphs \(G_ 1\) and \(G_ 2\) of equal size is defined as any graph of maximum size without isolated vertices that is isomorphic to a subgraph of both \(G_ 1\) and \(G_ 2\). The set of all greatest common subgraphs of \(G_ 1\) and \(G_ 2\) is denoted by \(\text{gcs} (G_ 1,G_ 2)\). If \(| \text{gcs} (G_ 1,G_ 2)|=1\), then \(G_ 1\) and \(G_ 2\) are said to have a unique greatest common subgraph. The author shows that with the exception of eight connected planar graphs every connected planar graph is the unique greatest common subgraph of two nonisomorphic connected planar graphs of equal size.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Planar graphs and greatest common subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687720)