Planar graphs and greatest common subgraphs (Q687720): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02988313 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2087845816 / rank | |||
Normal rank |
Latest revision as of 12:16, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Planar graphs and greatest common subgraphs |
scientific article |
Statements
Planar graphs and greatest common subgraphs (English)
0 references
28 October 1993
0 references
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.
0 references
greatest common subgraph
0 references
planar graphs
0 references
0 references