Универсальные циклы, порождающие все графы коалиционных разбиений циклов

Универсальные циклы, порождающие все графы коалиционных разбиений циклов

Глебов А. Н., Добрынин А. А.
Дискретный анализ и исследование операций, 32, 1, 16-27 (2025)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2025.32.807

Аннотация:

Коалицией в графе $G$ называется пара непересекающихся и недоминирующих подмножеств его вершин $V_1, V_2 \subset V (G)$ таких, что объединение $V_1 \cup V_2$ является доминирующим множеством. В коалиционном разбиении $\pi(G) = ${$V_1, V_2,  \dots , V_k$} каждое недоминирующее множество $V_i$ входит в некоторую коалицию с другим множеством этого разбиения, а если $V_i$ доминирующее, то оно одновершинное. Коалиционное разбиение вершин графа $G$ порождает граф коалиций $CG(G, \pi)$, в котором вершины соответствуют множествам разбиения и две вершины смежны, если соответствующие множества образуют коалицию. Известно, что в совокупности все простые циклы порядка более трёх порождают 26 графов коалиций с числом вершин не более шести. Универсальный цикл порождает все такие графы. В работе показано, что только циклы $C_{3k}$ при $k > 5$ универсальны. 

Табл. 4, ил. 1, библиогр. 25.

Литература:
  1. Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of domination in graphs. New York: Marcel Dekker, 1998. 464 p. (Pure Appl. Math.; V. 208). DOI: 10.1201/9781482246582.
     
  2. Du D.-Z., Wan P.-J. Connected dominating set: Theory and applications. New York: Springer, 2012. 206 p. (Springer Optim. Appl.; V. 77). DOI: 10. 1007/978-1-4614-5242-3.
     
  3. Henning M. A., Yeo A. Total domination in graphs. New York: Springer, 2013. 178 p. DOI: 10.1007/978-1-4614-6525-6.
     
  4. Topics in domination in graphs. Cham: Springer, 2020. 546 p. (Dev. Math.; V. 64). DOI: 10.1007/978-3-030-51117-3.
     
  5. Structures of domination in graphs. Cham: Springer, 2021. 536 p. (Dev. Math.; V. 66). DOI: 10.1007/978-3-030-58892-2.
     
  6. Domination in graphs: Core concepts. Cham: Springer, 2023. 644 p. DOI: 10. 1007/978-3-031-09496-5.
     
  7. Haynes T. W., Hedetniemi J. T., Hedetniemi S. T., McRae A. A., Mohan R. Introduction to coalitions in graphs // AKCE Int. J. Graphs Comb. 2020. V. 17, No. 2. P. 653–659. DOI: 10.1080/09728600.2020.1832874.
     
  8. Fisher St. D., Hobolt S. B. Coalition government and electoral accountability // Electoral Stud. 2010. V. 29, No. 3. P. 358–369. DOI: 10.1016/j. electstud.2010.03.003.
     
  9. Alikhani S., Bakhshesh D., Golmohammadi H. Total coalitions in graphs // Quaest. Math. 2024. V. 47, No. 11. P. 2283–2294. DOI: 10.2989/ 16073606.2024.2365365.
     
  10. Alikhani S., Bakhshesh D., Golmohammadi H., Konstantinova E. V. Connected coalitions in graphs // Discuss. Math. Graph Theory. 2024. V. 44, No. 4. P. 1551–1566. DOI: 10.7151/dmgt.2509.
     
  11. Alikhani S., Bakhshesh D., Golmohammadi H., Klavžar S. On independent coalition in graphs and independent coalition graphs // Discuss. Math. Graph Theory. 2025. V. 45, No. 2. P. 533–544. DOI: 10.7151/dmgt.2543.
     
  12. Golmohammadi H., Alikhani S., Ghanbari N., Takhonov I. I., Abaturov A. Strong coalitions in graphs. Ithaca, NY: Cornell Univ., 2024. 12 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2404.11575). DOI: 10.48550/arXiv. 2404.11575.
     
  13. Samadzadeh M. R., Mojdeh D. A. Independent coalition in graphs: Existence and characterization // Ars Math. Contemp. 2024. V. 24, No. 3. Article ID P3.09. 17 p. DOI: 10.26493/1855-3974.3113.6f7.
     
  14. Brešar B., Henning M. A., Klavžar S., Rall D. F. Domination games played on graphs. Cham: Springer, 2021, 122 p. DOI: 10.1007/ 978-3-030-69087-8.
     
  15. Bakhshesh D., Henning M. A. The minmin coalition number in graphs // Aequat. Math. 2024. V. 99. P. 223–236. DOI: 10.1007/s00010-024-01045-5.
     
  16. Bednarz P., Pirga M. On proper 2-dominating sets in graphs // Symmetry. 2024. V. 16, No. 3. Article ID 296. 10 p. DOI: 10.3390/sym16030296.
     
  17. Haynes T. W., Hedetniemi J. T., Hedetniemi S. T., McRae A. A., Mohan R. Coalition graphs // Commun. Comb. Optim. 2023. V. 8, No. 2. P. 423–430. DOI: 10.22049/CCO.2022.27916.1394.
     
  18. Bakhshesh D., Henning M. A., Pradhan D. On the coalition number of trees // Bull. Malays. Math. Sci. Soc. 2023. V. 46. Article ID 95. 14 p. DOI: 10.1007/s40840-023-01492-4.
     
  19. Haynes T. W., Hedetniemi J. T., Hedetniemi S. T., McRae A. A., Mohan R. Coalition graphs of paths, cycles, and trees // Discuss. Math. Graph Theory. 2023. V. 43, No. 4. P. 931–946. DOI: 10.7151/dmgt.2416.
     
  20. Haynes T. W., Hedetniemi J. T., Hedetniemi S. T., McRae A. A., Mohan R. Upper bounds on the coalition number // Australas. J. Comb. 2021. V. 80, No. 3. P. 442–453.
     
  21. Alikhani S., Golmohammadi H., Konstantinova E. V. Coalition of cubic graphs of order at most 10 // Commun. Comb. Optim. 2024. V. 9, No. 3. P. 437–450. DOI: 10.22049/cco.2023.28328.1507.
     
  22. Dobrynin A. A., Golmohammadi H. On cubic graphs having the maximum coalition number // Сиб. электрон. мат. изв. 2024. Т. 21, № 1. С. 356–362. DOI: 10.33048/semi.2024.21.027.
     
  23. Golmohammadi H. Total coalitions of cubic graphs of order at most 10 // Commun. Comb. Optim. 2024. V. 10, No. 3. P. 601–615. DOI: 10.22049/cco. 2024.29015.1813.
     
  24. Haynes T. W., Hedetniemi J. T., Hedetniemi S. T., McRae A. A., Mohan R. Self-coalition graphs // Opuscula Math. 2023. V. 43, No. 2. P. 173–183. DOI: 10.7494/opmath.2023.43.2.173.
     
  25. Bakhshesh D., Henning M. A., Pradhan D. Singleton coalition graph chains // Comput. Appl. Math. 2024. V. 43. Article ID 85. 22 p. DOI: 10.1007/s40314-023-02588-0.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0017).

Глебов Алексей Николаевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: angle@math.nsc.ru

Добрынин Андрей Алексеевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: dobr@math.nsc.ru

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

Abstract:

A coalition in a graph $G$ is a pair of disjoint nondominating subsets of its vertices $V_1, V_2 \subset V (G)$ such that $V_1 \cup V_2$ is a dominating set. In the coalition partition $\pi(G) = ${$V_1, V_2,  \dots , V_k$}, every nondominating set $V_i$ is included in some coalition and if $V_i$ is dominating, then it is a single-vertex set. A coalition partition of vertices of a graph $G$ generates a coalition graph $CG(G, \pi)$ whose vertices correspond to the partition sets, while two vertices are adjacent if the corresponding sets form a coalition. It is well known that all simple cycles of order greater than three generate in total 26 coalition graphs of order at most six. A universal cycle generates all such graphs. It is shown that only the cycles $C_{3k}, k > 5$, are universal. 

Tab. 4, illustr. 1, bibliogr. 25.

References:
  1. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998) (Pure Appl. Math., Vol. 208), DOI: 10.1201/9781482246582.
     
  2. D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications (Springer, New York, 2012) (Springer Optim. Appl., Vol. 77), DOI: 10.1007/978-1-4614-5242-3.
     
  3. M. A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013), DOI: 10.1007/978-1-4614-6525-6.
     
  4. Topics in Domination in Graphs (Springer, Cham, 2020) (Dev. Math., Vol. 64), DOI: 10.1007/978-3-030-51117-3. 
     
  5. Structures of Domination in Graphs (Springer, Cham, 2021) (Dev. Math., Vol. 66), DOI: 10.1007/978-3-030-58892-2.
     
  6. Domination in Graphs: Core Concepts (Springer, Cham, 2023), DOI: 10.1007/ 978-3-031-09496-5.
     
  7. T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2), 653–659 (2020), DOI: 10.1080/09728600.2020.1832874.
     
  8. St. D. Fisher and S. B. Hobolt, Coalition government and electoral accountability, Electoral Stud. 29 (3), 358–369 (2010), DOI: 10.1016/j.electstud. 2010.03.003.
     
  9. S. Alikhani, D. Bakhshesh, and H. Golmohammadi, Total coalitions in graphs, Quaest. Math. 47 (11), 2283–2294 (2024), DOI: 10.2989/16073606. 2024.2365365.
     
  10. S. Alikhani, D. Bakhshesh, H. Golmohammadi, and E. V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory. 44 (4), 1551–1566 (2024), DOI: 10.7151/dmgt.2509.
     
  11. S. Alikhani, D. Bakhshesh, H. Golmohammadi, and S. Klavžar, On independent coalition in graphs and independent coalition graphs, Discuss. Math. Graph Theory 45 (2), 533–544 (2025), DOI: 10.7151/dmgt.2543. 
     
  12. H. Golmohammadi, S. Alikhani, N. Ghanbari, I. I. Takhonov, and A. Abaturov, Strong coalitions in graphs (Cornell Univ., Ithaca, NY, 2024) (Cornell Univ. Libr. e-Print Archive, arXiv:2404.11575), DOI: 10.48550/ arXiv.2404.11575.
     
  13. M. R. Samadzadeh and D. A. Mojdeh, Independent coalition in graphs: Existence and characterization, Ars Math. Contemp. 24 (3), ID P3.09 (2024), DOI: 10.26493/1855-3974.3113.6f7.
     
  14. B. Brešar, M. A. Henning, S. Klavžar, and D. F. Rall, Domination Games Played on Graphs (Springer, Cham, 2021), DOI: 10.1007/ 978-3-030-69087-8.
     
  15. D. Bakhshesh and M. A. Henning, The minmin coalition number in graphs, Aequat. Math. 99, 223–236 (2024), DOI: 10.1007/s00010-024-01045-5.
     
  16. P. Bednarz and M. Pirga, On proper 2-dominating sets in graphs, Symmetry 16 (3), ID 296 (2024), DOI: 10.3390/sym16030296.
     
  17. T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2), 423–430 (2023), DOI: 10.22049/CCO.2022.27916.1394.
     
  18. D. Bakhshesh, M. A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46, ID 95 (2023), DOI: 10.1007/ s40840-023-01492-4.
     
  19. T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs of paths, cycles, and trees, Discuss. Math. Graph Theory. 43 (4), 931–946 (2023), DOI: 10.7151/dmgt.2416.
     
  20. T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Upper bounds on the coalition number, Australas. J. Comb. 80 (3), 442–453 (2021).
     
  21. S. Alikhani, H. Golmohammadi, and E. V. Konstantinova, Coalition of cubic graphs of order at most 10, Commun. Comb. Optim. 9 (3), 437–450 (2024), DOI: 10.22049/cco.2023.28328.1507.
     
  22. A. A. Dobrynin and H. Golmohammadi, On cubic graphs having the maximum coalition number, Sib. Elektron. Mat. Izv. 21 (1), 356–362 (2024), DOI: 10.33048/semi.2024.21.027.
     
  23. H. Golmohammadi, Total coalitions of cubic graphs of order at most 10, Commun. Comb. Optim. 10 (3), 601–615 (2024), DOI: 10.22049/cco.2024. 29015.1813.
     
  24. T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Self-coalition graphs, Opuscula Math. 43 (2), 173–183 (2023), DOI: 10.7494/opmath.2023.43.2.173.
     
  25. D. Bakhshesh, M. A. Henning, and D. Pradhan, Singleton coalition graph chains, Comput. Appl. Math. 43, ID 85 (2024), DOI: 10.1007/ s40314-023-02588-0.