×

Greatest common subgroups with specified properties. (English) Zbl 0672.05045

Summary: A graph G without isolated vertices is a greatest common subgraph of a set \({\mathcal G}\) of graphs, all having the same size, if G is a graph of maximum size that is isomorphic to a subgroup of every graph in \({\mathcal G}\). A number of results concerning greatest common subgraphs are presented. For several graphical properties \({\mathcal P}\), we discuss the problem of determining, for a given graph G with property \({\mathcal P}\), the existence of two non-isomorphic graphs \(G_ 1\) and \(G_ 2\) of equal size, also with property \({\mathcal P}\), such that G is the unique greatest common subgroup of \(G_ 1\) and \(G_ 2\). In particular, this problem is solved when \({\mathcal P}\) is the property of being 2-connected and when \({\mathcal P}\) is the property of having chromatic number n.

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G., Johnson, M., Oellermann, O.R.: Connected graphs containing a given connected graph as a unique greatest common subgraph. Aequationes Math.31, 213–222 (1986) · Zbl 0611.05056
[2] Chartrand, G., Lesniak, L.: Graphs & Digraphs, Second Edition. Monterey: Wadsworth & Brooks/Cole 1986 · Zbl 0666.05001
[3] Chartrand, G., Saba, F., Zou, H.B.: Edge rotations and distance between graphs. Cas. Pestovani Mat.110, 87–91 (1985) · Zbl 0567.05044
[4] Chartrand, G., Saba, F., Zou, H.B.: Greatest common subgraphs of graphs. Cas. Pestovani Mat.112, 80–88 (1987) · Zbl 0624.05057
[5] Chartrand, G., Zou, H.B.: Trees and greatest common subgraphs. Scientia. (to appear) · Zbl 0699.05023
[6] Erdös, P., Gallai, T.: Graphs with prescribed degrees of vertices (in Hungarian). Mat. Lapok11, 264–274 (1960) · Zbl 0103.39701
[7] Zelinka, B.: On a certain distance between isomorphic classes of graphs. Cas. Pestovani Mat.100, 371–373 (1975) · Zbl 0312.05121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.