Об асимптотическом перечислении помеченных последовательно-параллельных k-циклических графов

Об асимптотическом перечислении помеченных последовательно-параллельных $k$-циклических графов

Воблый В. А.
Дискретный анализ и исследование операций, 29, 4, 5-14 (2022)
Скачать статью

УДК 519.175.3 
DOI: 10.33048/daio.2022.29.732

Аннотация:

Получена асимптотика для числа помеченных связных последовательно-параллельных $k$-циклических $n$-вершинных графов при большом числе вершин и фиксированном числе $k$. Найдена вероятность того, что при равномерном вероятностном распределении случайный помеченный связный $n$-вершинный $k$-циклический граф при фиксированном $k$ и $n \to \infty$ является последовательно-параллельным графом. Кроме того, определена вероятность того, что случайный помеченный связный последовательно-параллельный $n$-вершинный $k$-циклический граф при фиксированном $k$ и $n \to \infty$ является кактусом.
Библиогр. 16.

Литература:
  1. Харари Ф. Теория графов. М.: Мир, 1973. 299 c.
     
  2. Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Comb. 2007. V. 28, No. 8. P. 2091–2105.
     
  3. McDiarmid C., Scott A. Random graphs from a block stable class // Eur. J. Comb. 2016. V. 58. P. 96–106.
     
  4. Raghavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. V. 43, No. 3. P. 163–176.
     
  5. Takamizawa K., Nishizeki T., Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // J. ACM. 1982. V. 29, No. 3. P. 623–641.
     
  6. Воблый В. А. Перечисление помеченных последовательно-параллельных трициклических графов // Итоги науки и техники. Сер. Соврем. математика и её прил. Темат. обзор. Т. 177. М.: ВИНИТИ РАН, 2020. C. 132–136.
     
  7. Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных тетрациклических графов // Итоги науки и техники. Сер. Соврем. математика и её прил. Темат. обзор. Т. 187. М.: ВИНИТИ РАН, 2020. C. 31–35.
     
  8. NIST handbook of mathematical functions. New York: Camb. Univ. Press, 2010. 951 p.
     
  9. Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и рёбер // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 5–20.
     
  10. Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990. 504 с.
     
  11. Риордан Дж. Комбинаторные тождества. М.: Наука, 1982. 256 c.
     
  12. Воблый В. А. Второе соотношение Риддела и следствия из него // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 1. С. 20–32.
     
  13. Wright E. M. The number of connected sparsely edged graphs // J. Graph Theory. 1977. V. 1, No. 4. P. 317–330. 
     
  14. Wright E. M. The number of connected sparsely edged graphs. II // J. Graph Theory. 1978. V. 2, No. 4. P. 299–305.
     
  15. Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных $k$-циклических графов без мостов // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 4. С. 61–69.
     
  16. Wright E. M. The number of connected sparsely edged graphs. III // J. Graph Theory. 1980. V. 4, No. 4. P. 393–407.
Воблый Виталий Антониевич
  1. Всероссийский институт научной и технической информации,
    ул. Усиевича, 20, 125190, Москва, Россия

E-mail: vitvobl@yandex.ru

Статья поступила 7 февраля 2022 г. 
После доработки — 17 апреля 2022 г. 
Принята к публикации 19 апреля 2022 г.

Abstract:

We deduce an asymptotic formula for the number of labeled connected series-parallel $k$-cyclic graphs with given order and fixed number $k$. Under uniform probability distribution, we find the probability that a random labeled connected $n$-vertex $k$-cyclic graph with a fixed $k$ and $n \to \infty$ is a series-parallel graph. In addition, we determine the probability that, under uniform probability distribution, a random labeled connected series-parallel $n$-vertex $k$-cyclic graph with a fixed $k$ and $n \to \infty$ is a cactus.
Bibliogr. 16.

References:
  1. F. Harary, Graph Theory (Addison-Wesley, London, 1969; Mir, Moscow, 1973 [Russian]).
     
  2. M. Bodirsky, O. Gimenez, M. Kang, and M. Noy, Enumeration and limit laws of series-parallel graphs, Eur. J. Comb. 28 (8), 2091–2105 (2007).
     
  3. C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb. 58, 96–106 (2016).
     
  4. S. Raghavan, Low-connectivity network design on series-parallel graphs, Networks 43 (3), 163–176 (2004).
     
  5. K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM 29 (3), 623–641 (1982).
     
  6. V. A. Voblyi, Enumeration of labeled series-parallel tricyclic graphs, Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 177 (VINITI RAN, Moscow, 2020), pp. 132–136 [Russian].
     
  7. V. A. Voblyi, Asymptotical enumeration of labeled series-parallel tetracyclic graphs, Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 187 (VINITI RAN, Moscow, 2020), pp. 31–35 [Russian].
     
  8. NIST Handbook of Mathematical Functions (Cambridge Univ. Press, New York, 2010).
     
  9. V. A. Voblyi, Enumeration of labeled connected graphs with given order and size, Diskretn. Anal. Issled. Oper. 23 (2), 5–20 (2016) [Russian] [J. Appl. Ind. Math. 10 (2), 302–310 (2016)].
     
  10. I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (John Wiley Sons, New York, 1983; Nauka, Moscow, 1990 [Russian]).
     
  11. J. Riordan, Combinatorial Identities (John Wiley Sons, New York, 1968; Nauka, Moscow, 1982 [Russian]).
     
  12. V. A. Voblyi, The second Riddell relation and its consequences, Diskretn. Anal. Issled. Oper. 26 (1), 20–32 (2019) [Russian] [J. Appl. Ind. Math. 13 (1), 168–174 (2019)].
     
  13. E. M. Wright, The number of connected sparsely edged graphs, J. Graph Theory 1 (4), 317–330 (1977).
     
  14. E. M. Wright, The number of connected sparsely edged graphs. II, J. Graph Theory 2 (4), 299–305 (1978).
     
  15. V. A. Voblyi, Asymptotical enumeration of labeled series-parallel k-cyclic bridgeless graphs, Diskretn. Anal. Issled. Oper. 28 (4), 61–69 (2021) [Russian] [J. Appl. Ind. Math. 15 (4) (2019)].
     
  16. E. M. Wright, The number of connected sparsely edged graphs. III, J. Graph Theory 4 (4), 393–407 (1980).