On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices
type: Item
instance of: scholarly article
title: On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices
zbMATH Open document ID: 1474.05104
author: Jan Mycielski
author: Grzegorz Tomkowicz
published in: Acta Mathematica Hungarica
publication date: 2021-06-29T00:00:00Z
review text: The paper under review deals with graphs whose automorphism group acts transitively on the vertices of the graph (which the authors call homogeneous graphs, some call them vertex-transitive). They are interested in the properties of being bi-edge-connected (what some authors would call 2-edge-connected) i.e. that removing any single edge does not disconnect the graph, the property (which they call R) that for any edge \(x\) there is some edge \(y\) (\(y\) may be \(x\)) such that removing \(x\) and \(y\) disconnects the graph, and the property that every connected subgraph of the graph has property R (which they call RH). \par For example, it is shown that any connected graph with maximum degree \(\leq 4\) which is homogeneous and has property RH falls into one of five classes. \par A related topic is 2-generated groups and free groups. For example, the authors show that if \(G\) is any group generated by two elements \(s\) and \(t\), then there is a subset \(E\subset G\) and \(p,q\in E\) such that \(sE=E\backslash \{p\}\) and \(tE=E\backslash \{q\}\) if and only if \(G\) is freely generated by \(s\) and \(t\) or it has a very particular presentation. \par The authors also pose some open problems.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 20E05
zbMATH DE Number: 7364727
zbMATH Keywords: bi-edge-connected graph
zbMATH Keywords: Cayley graph
zbMATH Keywords: free non-abelian group
zbMATH Keywords: graph with two removable vertices
zbMATH Keywords: structural characterization of families of graphs
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: s10474-020-01118-2
OpenAlex ID: W3127081866
cites work: On groups with weak Sierpi
cites work: About sets invariant with respect to denumerable changes
cites work: Paradoxical sets and sets with two removable points
cites work: Sur un ensemble plan singulier
cites work: On a problem of W. Sierpiński on the congruence of sets
cites work: On Sierpiński sets in groups
cites work: Visualizing paradoxical sets
cites work: The Banach-Tarski paradox
DOI: 10.1007/S10474-020-01118-2
description: scientific article; zbMATH DE number 7364727