DMGT

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

UNDIRECTED AND DIRECTED GRAPHS WITH NEAR POLYNOMIAL GROWTH

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

Abstract

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.

References

[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