The structure of neighbor disconnected vertex transitive graphs (Q1301706)

The ideas of the main theorem are introduced by pointing out that a disconnected vertex transitive graph with \(t\) connected components is in fact a wreath product of a connected vertex transitive graph and an empty graph of order \(t\). Moreover, such a graph is the complement of a vertex transitive graph which becomes empty after the removal of the closed neighborhood of a vertex. A graph is neighbor disconnected if the removal of the closed neighborhood of a vertex leaves a disconnected induced subgraph. After defining wreath product inducers as a technical tool, several structure theorems are proven: A nonempty graph admitting a left action of a group \(G\) is vertex transitive and neighbor disconnected if and only if it has a nontrivial wreath product factorization in which both factors are vertex transitive for some subgroup of \(G\). As an application wreath product decompositions of all connected, neighbor disconnected vertex transitive graphs of degrees not exceeding 10 are given. Finally, necessary and sufficient conditions for neighbor disconnection in terms of neighborhoods and orbits of the vertex whose closed neighborhood is deleted are developed, giving a different perspective on neighborhood disconnection which is particularly useful for Cayley graphs defined in terms of generating subsets of the group.