Symmetrical extensions of graphs

E. A. Neganova ; V. I. Trofimov

Izvestiya. Mathematics , Tome 78 (2014) no. 4, pp. 809-835

Résumé

We study symmetrical extensions of graphs, with special emphasis on symmetrical and $\operatorname{Aut}_{0}(\Lambda^{d})$-symmetrical extensions of $d$-dimensional grids $\Lambda^{d}$ by finite graphs. These topics are of interest in group theory and graph theory and possibly also in crystallography and some branches of physics. We prove the existence of a connected locally finite graph admitting infinitely many symmetrical extensions by a fixed finite graph. On the other hand, we prove that the number of symmetrical and $\operatorname{Aut}_{0}(\Lambda^{d})$-symmetrical extensions of the $d$-dimensional grid $\Lambda^{d}$ by a finite graph is finite in several interesting cases. Moreover, for every positive integer $d$ we construct all $\operatorname{Aut}_{0}(\Lambda^{d})$-symmetrical extensions of the $d$-dimensional grid $\Lambda^{d}$ by two-vertex graphs.

Détail

Keywords: symmetrical extensions of graphs, the Cayley graph of a group, $d$-dimensional grids, automorphisms of graphs.