Symmetrical extensions of graphs

DOI10.1070/IM2014V078N04ABEH002707MaRDI QIDQ2925763zbMATH OpenOpenAlexFDO

Publication date 17 October 2014

Published in Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1070/im2014v078n04abeh002707

\(d\)-dimensional grids automorphisms of graphs Cayley graph of a group symmetrical extensions of graphs

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Geometric group theory (20F65)

Review text

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\).

Recommendations

Cited in

(14)

This page was built for publication: Symmetrical extensions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925763)