О числе вечного доминирования планарных графов диаметра 2

О числе вечного доминирования планарных графов диаметра 2

Талецкий Д. С.
Дискретный анализ и исследование операций, 32, 1, 122-144 (2025)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2025.32.804

Аннотация:

Вечным доминирующим множеством графа называется доминирующее множество $D$, на котором располагается первоначально мобильная охрана (не более одного охранника может находиться в каждой вершине). Для любой бесконечной последовательности атак на вершины графа множество $D$ может быть модифицировано путём передвижения охранника со смежной вершины в атакуемую вершину (предполагается, что атакуемая вершина не была занята охранником во время атаки). Конфигурация охранников должна после каждой атаки и движения охранника образовывать доминирующее множество. Числом вечного доминирования графа называется мощность его наименьшего вечного доминирующего множества. Доказано, что число вечного доминирования каждого планарного графа диаметра 2 равно числу его кликового покрытия.

Ил. 5, библиогр. 10.

Литература:
  1. Burger A. P., Cockayne E. J., Grundlingh W. R., Mynhardt C. M., van Vuuren J., Winterbach W. Infinite order domination in graphs // J. Comb. Math. Comb. Comput. 2004. V. 50. P. 179–194.
     
  2. Goddard W., Hedetniemi S. M., Hedetniemi S. T. Eternal security in graphs // J. Comb. Math. Comb. Comput. 2005. V. 52. P. 169–180.
     
  3. Klostermeyer W. F., MacGillivray G. Eternal security in graphs of fixed independence number // J. Comb. Math. Comb. Comput. 2007. V. 63. P. 97–101.
     
  4. Goldwasser J. L., Klostermeyer W. F. Tight bounds for eternal dominating sets in graphs // Discrete Math. 2008. V. 308, No. 12. P. 2589–2593.
     
  5. Driscoll K., Klostermeyer W. F., Krop E., Magnant C., Taylor P. On eternal domination and Vizing-type inequalities // AKCE Int. J. Graphs Comb. 2020. V. 17, No. 1. P. 1–5.
     
  6. Klostermeyer W., Mynhardt C. Protecting a graph with mobile guards // Appl. Anal. Discrete Math. 2016. V. 10. P. 1–29.
     
  7. Topics in domination in graphs. Cham: Springer, 2020. 546 p. (Dev. Math.; V. 64).
     
  8. Anderson M., Barrientos C., Brigham R., Carrington J., Vitray R., Yellen J. Maximum-demand graphs for eternal security // J. Comb. Math. Comb. Comput. 2007. V. 61. P. 111–128.
     
  9. Krim-Yee A., Seamone B., Virgile V. Eternal domination on prisms of graphs // Discrete Appl. Math. 2019. V. 283. P. 734–736.
     
  10. MacGillivray G., Mynhardt C. M., Virgile V. Eternal domination and clique covering // Electron. J. Graph Theory Appl. 2022. V. 10, No. 2. P. 603–624.

Исследование выполнено в рамках Программы фундаментальных исследований Национального исследовательского университета «Высшая школа экономики». Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Талецкий Дмитрий Сергеевич
  1. Национальный исследовательский университет «Высшая школа экономики», 
    ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия

E-mail: dmitalmail@gmail.com

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

Abstract:

An eternal dominating set in a graph is a dominating set $D$ on which mobile guards are initially located (at most one guard is allowed on any vertex). For any infinite sequence of attacks occurring sequentially at vertices, the set $D$ can be modified by moving the guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number of a graph is the cardinality of its minimum eternal dominating set. We prove that the eternal domination number of any planar graph of diameter 2 is equal to its clique covering number. 

Illustr. 5, bibliogr. 10.

References:
  1. A. P. Burger, E. J. Cockayne, W. R. Grundlingh, C. M. Mynhardt, J. van Vuuren, and W. Winterbach, Infinite order domination in graphs, J. Comb. Math. Comb. Comput. 50, 179–194 (2004).
     
  2. W. Goddard, S. M. Hedetniemi, and S. T. Hedetniemi, Eternal security in graphs, J. Comb. Math. Comb. Comput. 52, 169–180 (2005).
     
  3. W. F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Comb. Math. Comb. Comput. 63, 97–101 (2007).
     
  4. J. L. Goldwasser and W. F. Klostermeyer, Tight bounds for eternal dominating sets in graphs, Discrete Math. 308 (12), 2589–2593 (2008).
     
  5. K. Driscoll, W. F. Klostermeyer, E. Krop, C. Magnant, and P. Taylor, On eternal domination and Vizing-type inequalities, AKCE Int. J. Graphs Comb. 17 (1), 1–5 (2020).
     
  6. W. Klostermeyer and C. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10, 1–29 (2016).
     
  7. Topics in Domination in Graphs (Springer, Cham, 2020) (Dev. Math., Vol. 64).
     
  8. M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray, and J. Yellen, Maximum-demand graphs for eternal security, J. Comb. Math. Comb. Comput. 61, 111–128 (2007).
     
  9. A. Krim-Yee, B. Seamone, and V. Virgile, Eternal domination on prisms of graphs, Discrete Appl. Math. 283, 734–736 (2019).
     
  10. G. MacGillivray, C. M. Mynhardt, and V. Virgile, Eternal domination and clique covering, Electron. J. Graph Theory Appl. 10 (2), 603–624 (2022).