On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices (Q2036576)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices |
scientific article |
Statements
On some 2-edge-connected homogenous graphs and Cayley graphs with two removable vertices (English)
0 references
29 June 2021
0 references
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.
0 references
bi-edge-connected graph
0 references
Cayley graph
0 references
free non-abelian group
0 references
graph with two removable vertices
0 references
structural characterization of families of graphs
0 references