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.

Bibliographie

[1] V. I. Trofimov, “Symmetrical extensions of graphs and some other topics in graph theory related with group theory”, Tr. IMM UrO RAN, 17:4 (2011), 316–320 ; Proc. Steklov Inst. Math. (Suppl.), 279{, suppl. 1} (2012), 107–112 | DOI

[2] W. Imrich, S. Klavžar, Product graphs. Structure and recognition, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000, xvi+358 pp. | MR | Zbl

[3] V. I. Trofimov, “Graphs with polynomial growth”, Math. USSR-Sb., 51:2 (1985), 405–417 | DOI | MR | Zbl

[4] W. Woess, “Topological groups and recurrence of quasi tranitive graphs”, Rend. Sem. Mat. Fis. Milano, 64:1 (1996), 185–213 | DOI | MR | Zbl

[5] V. I. Trofimov, “Automorphisms of graphs and a characterization of lattices”, Math. USSR-Izv., 22:2 (1984), 379–391 | DOI | MR | Zbl

[6] M. B. Green, J. H. Schwarz, E. Witten, Superstring theory, v. 1, 2, Cambridge Monogr. Math. Phys., Cambridge Univ. Press, Cambridge, 1987, x+469 pp., xii+596 pp. | MR | MR | MR | MR | Zbl

[7] E. A. Neganova, V. I. Trofimov, “On symmetrical $q$-extensions of the 2-dimensional grid”, Proc. Steklov Inst. Math. (Suppl.), 272{, suppl. 1} (2011), 127–137 | DOI | Zbl

[8] E. A. Neganova, V. I. Trofimov, “O simmetricheskikh $4$-rasshireniyakh $2$-mernoi reshetki”, Tr. IMM UrO RAN, 17:3 (2011), 242–257

[9] E. A. Neganova, “$\mathrm{Aut}_0(\Lambda^2)$symmetrical 4-extensions of the 2-dimensional grid $\Lambda^2$”, Proc. Steklov Inst. Math. (Suppl.), 279{, suppl. 1} (2012), 84–106 | DOI

[10] N. Seifter, V. I. Trofimov, “Automorphism groups of graphs with quadratic growth”, J. Combin. Theory Ser. B, 71:2 (1997), 205–210 | DOI | MR | Zbl

[11] G. Baumslag, R. Strebel, M. W. Thomson, “On the multiplicator of $F/\gamma_{c}R$”, J. Pure Appl. Algebra, 16:2 (1980), 121–132 | DOI | MR | Zbl

[12] A. Yu. Ol'shanskiĭ, Geometry of defining relations in groups, Math. Appl. (Soviet Ser.), 70, Kluwer Acad. Publ., Dordrecht, 1991, xxvi+505 pp. | DOI | MR | MR | Zbl | Zbl

[13] F. Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.–Menlo Park, Calif.–London, 1969, ix+274 pp. | MR | MR | Zbl | Zbl

[14] F. Harary, E. M. Palmer, Graphical enumeration, Academic Press, New York–London, 1973, xiv+271 pp. | MR | MR | Zbl

[15] E. A. Neganova, V. I. Trofimov, “$\operatorname{Aut}_{0}(\Lambda^{d})$-simmetricheskie 2-rasshireniya reshetok $\Lambda^{d}$”, Tez. dokladov $41$-i Vserossiiskoi molodezhnoi konferentsii “Problemy teoreticheskoi i prikladnoi matematiki”, IMM UrO RAN, Ekaterinburg, 2010, 64–70