Перечисление помеченных графов библоков

Перечисление помеченных графов библоков

Воблый В. А.
Дискретный анализ и исследование операций, 30, 4, 24–34 (2023)
Скачать статью

УДК 519.175.3 
DOI: 10.33048/daio.2023.30.778

Аннотация:

Граф библоков — это связный граф, у которого все блоки являются полными двудольными графами. В статье перечислены по числу вершин точно и асимптотически помеченные графы библоков и графы библоков без мостов. Доказано, что почти все помеченные связные графы библоков не имеют мостов. Кроме того, перечислены помеченные планарные графы библоков и найдена асимптотическая оценка для числа таких графов. 
Табл. 1, библиогр. 12.

Литература:
  1. Hou Y., Sun Y. Inverse of distance matrix of a bi-block graphs // Linear Multilinear Algebra. 2016. V. 64, No. 8. P. 1509–1517.
     
  2. McDiarmid C., Scott A. Random graphs from a block stable class // Eur. J. Comb. 2016. V. 58. P. 96–106.
     
  3. Singh R. Permanent, determinant, and rank bi-block graphs // Aequationes Math. 2020. V. 94, No. 1. P. 1–12.
     
  4. Das J., Mohanty S. On spectral radius of bi-block graphs with given independence number $\alpha$ // Appl. Math. Comput. 2021. V. 402. Paper ID 125912. 8 p.
     
  5. Harary F., Robinson R. W. Labeled bipartite blocks // Can. J. Math. 1979. V. 31, No. 1. P. 60–68.
     
  6. Gross J. L., Yellen J. Graph theory and its applications. New York: Chapman and Hall/CRC, 2005. 800 p.
     
  7. Харари Ф. Теория графов. М.: Мир, 1973. 299 с.
     
  8. Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 4. С. 48–59.
     
  9. Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990. 504 с.
     
  10. Воблый В. А. Второе соотношение Риддела и следствия из него // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 1. С. 20–32.
     
  11. Flajolet P., Sedgewick R. Analytic combinatorics. Cambridge, UK: Camb. Univ. Press, 2009. 810 p.
     
  12. Воблый В. А. О перечислении помеченных связных графов без мостов // Итоги науки и техники. Сер. Соврем. математика и её прил. Темат. обзоры. Т. 223. М.: ВИНИТИ РАН, 2023. С. 138–147.
Воблый Виталий Антониевич
  1. Всероссийский институт научной и технической информации РАН, 
    ул. Усиевича, 20, 125190 Москва, Россия

E-mail: vitvobl@yandex.ru

Статья поступила 12 июля 2023 г. 
После доработки — 4 августа 2023 г. 
Принята к публикации 20 августа 2023 г.

Abstract:

A bi-block graph is a connected graph in which all blocks are complete bipartite graphs. Labeled bi-block graphs and bridgeless bi-block graphs are enumerated exactly and asymptotically by the number of vertices. It is proved that almost all labeled connected bi-block graphs have no bridges. In addition, planar bi-block graphs are enumerated, and an asymptotic estimate is found for the number of such graphs. 
Tab. 1, bibliogr. 12.

References:
  1. Y. Hou and Y. Sun, Inverse of distance matrix of a bi-block graphs, Linear Multilinear Algebra 64 (8), 1509–1517 (2016).
     
  2. C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb. 58, 96–106 (2016).
     
  3. R. Singh, Permanent, determinant, and rank bi-block graphs, Aequationes Math. 94 (1), 1–12 (2020).
     
  4. J. Das and S. Mohanty, On spectral radius of bi-block graphs with given independence number $\alpha$, Appl. Math. Comput. 402, Paper ID 125912 (2021).
     
  5. F. Harary and R. W. Robinson, Labeled bipartite blocks, Can. J. Math. 31 (1), 60–68 (1979).
     
  6. J. L. Gross and J. Yellen, Graph Theory and Its Applications (Chapman and Hall/CRC, New York, 2005).F. 
     
  7. Harary, Graph Theory (Addison-Wesley, London, 1969; Mir, Moscow, 1973 [Russian]). 
     
  8. V. A. Voblyi, On a formula for the number of labeled connected graphs, Diskretn. Anal. Issled. Oper. 19 (4), 48–59 (2012) [Russian].
     
  9. I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (John Wiley & Sons, New York, 1983; Nauka, Moscow, 1990 [Russian]).
     
  10. 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)].
     
  11. P. Flajolet and R. Sedgewick, Analytic Combinatorics (Camb. Univ. Press, Cambridge, UK, 2009).
     
  12. V. A. Voblyi, On enumeration of labeled connected bridgeless graphs, in Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 223 (VINITI RAN, Moscow, 2023), pp. 138–147 [Russian].