ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG 1 andG 2 of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG 1 andG 2. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01788654
Permalink