Об экстремальных двусвязных графах с фиксированным диаметром

Об экстремальных двусвязных графах с фиксированным диаметром

Белоцерковский Д. Л.
Дискретный анализ и исследование операций, 32, 4, 69-101 (2025)
Скачать статью

УДК 519.176 
DOI: 10.33048/daio.2025.32.815

Аннотация:

Рассматриваются две задачи теории экстремальных графов. Первая задача сформулирована и полностью доказана в виде теоремы о точной нижней границе числа рёбер для двусвязных графов с диаметром, не превосходящим некоторого фиксированного значения. В процессе доказательства разработан метод перераспределения вкладов, который в дальнейшем применяется для решения второй задачи: перечисления графов, на которых найденная граница достигается. Так как задача перечисления графов весьма трудна и ранее в общем виде не решалась, на базе разработанного метода перечислены все так называемые предельные графы. Задача нахождения всех предельных графов сформулирована и доказана в виде второй теоремы статьи. Далее объясняется, почему именно предельные графы наиболее интересны с точки зрения задачи перечисления, а также приведены приёмы генерации остальных экстремальных графов с помощью уже полученных предельных графов. 

Ил. 11, библиогр. 21.

Литература:
  1. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. 192 с.
     
  2. Зайченко Ю. П. Задачи проектирования структуры распределённых вычислительных сетей // Автоматика. 1981. № 4. С. 27–40.
     
  3. Вишневский В. М., Савинецкий А. Б., Федотов Е. В. Анализ и реализация одного метода повышения производительности сети пакетной коммутации // Автоматика и вычисл. техника. 1987. № 2. С. 24–30.
     
  4. Фараджев И. А. Генерирование неизоморфных графов с заданным распределением степеней вершин // Алгоритмические исследования в комбинаторике. М.: Наука, 1978. С. 11–19.
     
  5. Murty U. S. R. On some extremal graphs // Acta Math. Acad. Sci. Hung. 1968. V. 19. P. 69–74.
     
  6. Murty U. S. R. Extremal nonseparable graphs of diameter 2 // Proof techniques in graph theory. Proc. 2nd Ann Arbor Graph Theory Conf. (Ann Arbor, USA, Feb., 1968). New York: Acad. Press, 1969. P. 111–117.
     
  7. Caccetta L. Extremal graphs of diameter 3 // J. Austral. Math. Soc. 1979. V. A28, No. 1. P. 63–84.
     
  8. Caccetta L. On extremal graphs with given diameter and connectivity // Ann. New York Acad. Sci. Topics Graph Theory. 1979. V. 328. P. 76–94.
     
  9. Caccetta L. Extremal graphs of diameter 4 // J. Comb. Theory, Ser. B. 1976. V. 21. P. 104–115.
     
  10. Белоцерковский Д. Л. Характеризация некоторых экстремальных графов с диаметром не превосходящим трёх // Дискрет. математика. 1997. Т. 9, № 1. С. 134–146.
     
  11. Белоцерковский Д. Л. Об одной задаче перечисления образующих графов с ограничением на диаметр // Пробл. управления. 2010. № 1. С. 2–6.
     
  12. Belotserkovsky D. L. The smallest number of edges in a 2-connected graph with specified diameter // Discrete Math. 2007. V. 307, No. 19–20. P. 2376–2384.
     
  13. Харари Ф. Теория графов. М.: Мир, 1973. 300 с.
     
  14. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 327 с.
     
  15. Bollobas B. Strongly two-connected graphs // Proc. 7th Southeastern Conf. Combinatorics, Graph Theory, and Computing (Baton Rouge, USA, Feb. 9–12, 1976). Winnipeg, Man.: Utilitas Math., 1976. P. 161–170. (Congr. Numer.; V. 17).
     
  16. Bollobas B. Extremal graph theory. London: Acad. Press, 1978. 488 p.
     
  17. Bollobas B. Extremal graph theory. Mineola: Dover Publ., 2004. 512 p.
     
  18. Bollobas B. Modern graph theory. New York: Springer, 1998. 394 p. (Graduate Texts Math.; V. 184).
     
  19. Bollobas B. Modern graph theory. Heidelberg: Springer, 2013. 408 p.
     
  20. Lovasz L. Large networks and graph limits. Hoboken, NJ: AMS, 2012. 475 p.
     
  21. Jarry A., Laugier A. On the minimum number of edges of two-connected graphs with given diameter // Discrete Math. 2012. V. 312. P. 757–762.

Исследование выполнено за счёт бюджета Российского гос. университета нефти и газа (НИУ) им. И. М. Губкина. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Белоцерковский Дмитрий Леонидович
  1. Российский гос. университет нефти и газа (НИУ) им. И. М. Губкина, 
    Ленинский пр., 65, 119991 Москва, Россия

E-mail: belozer68@mail.ru 

Статья поступила 18 октября 2024 г.
После доработки — 2 июня 2025 г.
Принята к публикации 22 июня 2025 г.

Abstract:

The article considers two problems in the extremal graph theory. The first problem is formulated and completely proved as a theorem on the exact lower bound for the number of edges in a biconnected graph of diameter not exceeding a given value. A discharging method is developed and used to solve the second problem: Enumerating the graphs for which the lower bound is attained. Since the problem of enumerating graphs is very difficult and has not been solved in general form before, all the so-called limit graphs are enumerated on the basis of the discharging method. The problem of finding all limit graphs is formulated and proved as the second theorem in the article. Further, we explain why limit graphs are the most promising for the enumeration problem, and give some techniques for constructing extremal graphs using the limit graphs already obtained. 

Illustr. 11, bibliogr. 21.

References:
  1. V. A. Zhozhikashvili and V. M. Vishnevskiy, Queueing Networks: Theory and Application to Computer Networks (Radio Svyaz, Moscow, 1988) [Russian].
     
  2. Yu. P. Zaychenko, Problems of design for distributed computing networks, Avtomatika, No. 4, 27–40 (1981) [Russian].
     
  3. V. M. Vishnevskiy, A. B. Savinetskiy, and E. V. Fedotov, Analysis and implementation of one method to improve the performance of a packet switching network, Avtom. Vychisl. Tekh., No. 2, 24–30 (1987) [Russian].
     
  4. I. A. Faradzhev, Generating non-isomorphic graphs with a given distribution of vertex degrees, in Algorithmic Research in Combinatorics (Nauka, Moscow, 1978), pp. 11–19 [Russian].
     
  5. U. S. R. Murty, On some extremal graphs, Acta Math. Acad. Sci. Hung. 19, 69–74 (1968).
     
  6. U. S. R. Murty, Extremal nonseparable graphs of diameter 2, in Proof Techniques in Graph Theory, Proc. 2nd Ann Arbor Graph Theory Conf. (Ann Arbor, USA, Feb., 1968) (Acad. Press, New York, 1969), pp. 111–117.
     
  7. L. Caccetta, Extremal graphs of diameter 3, J. Austral. Math. Soc. A28 (1), 63–84 (1979).
     
  8. L. Caccetta, On extremal graphs with given diameter and connectivity, Ann. New York Acad. Sci. Topics Graph Theory 328, 76–94 (1979).
     
  9. L. Caccetta, Extremal graphs of diameter 4, J. Comb. Theory, Ser. B, 21, 104–115 (1976).
     
  10. D. L. Belotserkovsky, Characterization of some extremal graphs with diameter not exceeding three, Diskretn. Mat. 9 (1), 134–146 (1997) [Russian] [Discrete Math. Appl. 7 (2), 163–176 (1997)].
     
  11. D. L. Belotserkovsky, On a problem of enumeration of generating graphs with a diameter constraint, Probl. Upr., No. 1, 2–6 (2010) [Russian].
     
  12. D. L. Belotserkovsky, The smallest number of edges in a 2-connected graph with specified diameter, Discrete Math. 307 (19–20), 2376–2384 (2007).
     
  13. F. Harary, Graph Theory (Addison-Wesley, London, 1969; Mir, Moscow, 1973 [Russian]).
     
  14. F. Harary and E. M. Palmer, Graphical Enumeration (Acad. Press, New York, 1973; Mir, Moscow, 1977 [Russian]). 
     
  15. B. Bollobas, Strongly two-connected graphs, in Proc. 7th Southeastern Conf. Combinatorics, Graph Theory, and Computing (Baton Rouge, USA, Feb. 9–12, 1976) (Utilitas Math., Winnipeg, Man., 1976), pp. 161–170 (Congr. Numer., Vol. 17).
     
  16. B. Bollobas, Extremal Graph Theory (Acad. Press, London, 1978).
     
  17. B. Bollobas, Extremal Graph Theory (Dover Publ., Mineola, 2004).
     
  18. B. Bollobas, Modern Graph Theory (Springer, New York, 1998) (Graduate Texts Math., Vol. 184).
     
  19. B. Bollobas, Modern Graph Theory (Springer, Heidelberg, 2013).
     
  20. L. Lovasz, Large Networks and Graph Limits (AMS, Hoboken, NJ, 2012).
     
  21. A. Jarry and A. Laugier, On the minimum number of edges of two-connected graphs with given diameter, Discrete Math. 312, 757–762 (2012).