ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 23(2) (2003) 383-391
DOI: 10.7151/dmgt.1208


V.I. Trofimov

Institute of Mathematics and Mechanics
Russian Academy of Sciences
Ekaterinburg, Russia

To Professor Wilfried Imrich on the occasion of his 60th birthday


The growth function of a graph with respect to a vertex is near polynomial if there exists a polynomial bounding it above for infinitely many positive integers. In the paper vertex-symmetric undirected graphs and vertex-symmetric directed graphs with coinciding in- and out-degrees are described in the case their growth functions are near polynomial.

Keywords: vertex-symmetric graph; vertex-symmetric directed graph; near polynomial growth; multivalued mapping.

2000 Mathematics Subject Classification: 05C25, 20F65, 37Bxx, 58C06.


[1]V. Trofimov, Graphs with polynomial growth, Math. USSR Sb. 51 (1985) 405-417, doi: 10.1070/SM1985v051n02ABEH002866.
[2]M. Gromov, Groups of polynomial growth and expanding maps, Publ. Math. IHES 53 (1981) 53-78, doi: 10.1007/BF02698687.
[3]L. van den Dries and A. Wilkie, Gromov's theorem on groups of polynomial growth and elementary logic, J. Algebra 89 (1984) 349-374, doi: 10.1016/0021-8693(84)90223-0.
[4]A. Veselov, Integrable mapping, Russian Math. Surveys 46 (1991) (5) 1-51.
[5]V. Trofimov, Automorphism groups of graphs as topological groups, Math. Notes 38 (1985) 717-720, doi: 10.1007/BF01163706.
[6]V. Trofimov, Directed graphs with polynomial growth, in: III Internat. Conf. Algebra (Krasnoyarsk, 1993), Abstracts of Reports, Krasnoyarsk State Univ. and Inst. Math. Siberian Branch Russian Acad. Sci. (Krasnoyarsk, 1993) 334-335 (in Russian).
[7]V. Trofimov, Certain asymptotic characteristics of groups, Math. Notes 46 (1989) 945-951, doi: 10.1007/BF01158632.
[8]R. Grigorchuk, Semigroups with cancellations of degree growth, Math. Notes 43 (1988) 175-183, doi: 10.1007/BF01138837.

Received 1 October 2001
Revised 15 February 2002