On a problem of Cameron's on inexhaustible graphs (Q1882142)

The authors prove a series of primarily negative results related to the question of P. J. Cameron, which countable graphs \(G\) have the property that deleting any vertex of \(G\) results in a graph that is isomorphic to \(G\). These graphs are called inexhaustible. They prove that the class of countable inexhaustible graphs together with the lexicographical product is a subsemigroup of the substition monoid that lacks many of the familiar properties of semigroups. They consider locally finite countable inexhaustible graphs and prove for instance that locally finite forests \(F\) having finitely many infinite components \(T_i\) each having none or finitely many endvertices are inexhaustible if and only if each \(T_i\) is a ray and \(F\) is age-closed. On the other hand they provide \(2^{\aleph_0}\) examples of locally finite inexhaustible forests with an infinite number of infinite components. Similarly, they provide \(2^{\aleph_0}\) examples of inexhaustible graphs that share many properties with the infinite random graph. Finally, they extend a result of \textit{M. El-Zahar} and \textit{N. Sauer} [Combinatorica 14, 159-165 (1994; Zbl 0803.05043)] on countable homogenoeus graphs that are inexhaustible.