Том 20, номер 6, 2013 г., Стр. 40-58

УДК 519.1
Исаев М. И., Исаева К. В.
Асимптотическое перечисление эйлеровых ориентаций в графах, обладающих сильными перемешивающими свойствами

Аннотация:
Рассмотрена задача подсчёта числа эйлеровых ориентаций в простых связных графах, все вершины которых имеют чётную степень. Для класса графов, обладающих сильными перемешивающими свойствами, получена асимптотическая формула, позволяющая определить искомое значение с точностью до мультипликативной ошибки $O(n^{-1+\varepsilon})$, где $n$ – число вершин.
Библиогр. 14.

Ключевые слова: эйлерова ориентация, асимптотический анализ, гауссовский интеграл, алгебраическая связность, матрица Лапласа.

Исаев Михаил Исмаилович ^1,2
Исаева Ксения Валерьевна ^1,2
1. Centre de Mathématiques Appliquées, École Polytechnique,
91128 Palaiseau, France
2. Московский физико-технический институт,
пер. Институтский, 9, 141700 Долгопрудный, Россия
е-mail: Isaev.M.I@gmail.com, Isaeva.K.V@gmail.com

Статья поступила 17 октября 2012 г.
Исправленный вариант — 29 марта 2013 г.

Литература

[1] Исаев М. И. Асимптотическое поведение числа эйлеровых ориентаций в графах // Мат. заметки. - 2013. - Т. 93, вып. 6. - C. 828–843.

[2] Biggs N. L., Lloyd E. K., Wilson R. J. Graph theory. - Oxford: Clarendon Press, 1976. - P. 1736–1936.

[3] Brightwell G., Winkler P. Note on counting Eulerian circuits // Proc. 7th ALENEX and 2nd ANALCO 2005. - P. 259–262. arXiv:cs/0405067v1.

[4] Chung F. Spectral graph theory // CBMS Regional Conf. Ser. Math. - Vol. 92. - New York: AMS, 1997. - P. 207.

[5] Fiedler M. Algebraic connectivity of graphs // Czech. Math. J. - 1973. - Vol. 23. - P. 298–305.

[6] Kirchhoff G. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird // Ann. Phys. Chem. - 1847. - Vol. 72. - P. 497–508. Engl. Transl in I.R.E. Trans. Circuit Theory, CT-5. - 1958. - Vol. 4. - P. 4–7.

[7] Las Vergnas M. Le polynôme de Martin d’un graphe Eulérien // Ann. Discrete Math. -1983. - Vol. 17. - P. 397–411.

[8] Las Vergnas M. An upper bound for the number of Eulerian orientations of a regular graph // Combinatorica. - 1990. - Vol. 10. - P. 61–65.

[9] Lovasz L. Random walks on graphs: a survey // Combinatorics: Paul Erdös is eighty. - Budapest: Janos Bolyai Math. Soc., 1996. - Vol. 2, - P. 353–397.

[10] Mihail M., Winkler P. On the number of Eulerian orientations of a graph // Algorithmica. - 1996. - Vol. 16. - P. 402-414.

[11] McKay B. D. The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs // Combinatorica. - 1990. - Vol. 10, N 4. - P. 367–377.

[12] Mohar B. Isoperimetric numbers of graphs // J. Comb. Theory. Ser. B. - 1989. - Vol. 47, N 3. - P. 274–291.

[13] Mohar B. The Laplacian spectrum of graphs // Graph theory, combinatorics, and applications. Vol. 2. - 1991. - P. 871–898.

[14] Schrijver A. Bounds on the number of Eulerian orientations // Combinatorica. - 1983. - Vol. 3. - P. 375–380.