Symmetrical extensions of graphs (Q2925763)

In how many and in which ways can one extend one graph symmetrically by another? The authors study one broad case of this question and provide some general conclusions.NEWLINENEWLINENEWLINE The connected graph \(\tilde\Gamma\) is a symmetric extension of \(\Gamma\) by \(\Delta\) (realized by \((\sigma,\phi)\)) if (i) there exists a vertex transitive group \(\tilde G\) of automorphisms of \(\tilde\Gamma\) and (ii) a system of imprimitivity \(\sigma\) of the vertices of \(\tilde\Gamma\) for \(\tilde G\) with the property that \(\phi\) induces an isomorphism between \(\tilde\Gamma/\sigma\) and \(\Gamma\), and the blocks of \(\sigma\) generate subgraphs of \(\tilde\Gamma\) isomorphic to \(\Delta\). For example, whenever \(\Gamma\) and \(\Delta\) have vertex transitive groups of automorphisms and \(\Gamma\) has at least two vertices, then the lexicographic product of \(\Gamma\) and \(\Delta\) is a symmetric extension of \(\Gamma\) by \(\Delta\). If in addition \(\tilde G^\sigma\) denotes the group of automorphisms induced on \(\tilde\Gamma/\sigma\) by \(\tilde G\) and \(\phi G^\sigma \phi^{-1} = G\), then they call \(\tilde\Gamma\) a \(G\)-symmetric extension of \(\Gamma\) by \(\Delta\). The authors' interest lies in symmetric extensions of infinite, locally finite graphs, especially in \(\mathrm{Aut}_0(\Lambda^d)\)-symmetric extensions of \(d\)-dimensional grids \(\Lambda^d\) by a finite graph \(\Delta\), where \(\mathrm{Aut}_0(\Lambda^d)\) denotes the group of shifts of \(\Lambda^d\). They pose the following three part question:NEWLINENEWLINENEWLINE (1) Is the number of such symmetric extensions finite; especially, (2) is the number of \(\mathrm{Aut}_0(\Lambda^d)\)-symmetric extensions finite, and if so, (3) can one describe them?NEWLINENEWLINENEWLINEThey obtain partial results for each of these parts, answering the first part in the negative in general by constructing a large class of locally finite graphs \(\Gamma_{G,M}\), a Cayley graph for a group \(G\) and a finite generating set \(M\), admitting infinitely many symmetric extensions by finite graphs. They answer the second part in the affirmative provided the number of vertices of \(\Delta\) is prime (but see their corollary 4.4 for a more general statement). They achieve this by verifying that any such extension satisfies a condition that they call periodicity from which the finiteness-in-number follows easily. For the final part, they construct all such graphs for arbitrary \(d\) and any two-vertex graph \(\Delta\).