Connected graphs containing a given connected graph as a unique greatest common subgraph (Q1087564)
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 3987334
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Connected graphs containing a given connected graph as a unique greatest common subgraph |
scientific article; zbMATH DE number 3987334 |
Statements
Connected graphs containing a given connected graph as a unique greatest common subgraph (English)
0 references
1986
0 references
A greatest common subgraph of two nonisomorphic graphs \(G_ 1\) and \(G_ 2\) of equal size is any graph of maximum size without isolated vertices that is a subgraph of both \(G_ 1\) and \(G_ 2\), see i.e. \textit{G. Chartrand, F. Saba} and \textit{H. Zou} [Čas. Pěstování Mat. 110, 87-91 (1985; Zbl 0567.05044)]. Here the authors determine those connected graphs G for which there exist nonisomorphic connected graphs of equal size with G as a unique greatest common subgraph. Analogous results are proved for induced subgraphs and subdigraphs.
0 references
greatest common subgraph
0 references
induced subgraphs
0 references
subdigraphs
0 references
0.903834342956543
0 references
0.9036482572555542
0 references
0.9031201004981996
0 references
