On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices
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.
structural characterization of families of graphs
scientific article; zbMATH DE number 7364727