О количестве k-доминирующих независимых множеств в планарных графах

О количестве $k$-доминирующих независимых множеств в планарных графах

Талецкий Д. С.
Дискретный анализ и исследование операций, 31, 1, 109–128 (2024)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2024.31.770

Аннотация:

Множество $J_k$ вершин графа называется $k$-доминирующим независимым $(k \ge 1)$, если его вершины попарно не смежны и каждая вершина не из $J_k$ смежна хотя бы с $k$ вершинами из $J_k$. В этой статье получены новые оценки количества $k$-доминирующих независимых множеств при различных значениях $k \ge 2$ в некоторых классах планарных графов. 
Ил. 7, библиогр. 15.

Литература:
  1. Nagy Z. L. On the number of $k$-dominating independent sets // J. Graph Theory. 2017. V. 84, No. 4. P. 566–580.
     
  2. Gerbner D., Keszegh B., Methuku A., Patkós B., Vizer M. An improvement on the maximum number of $k$-dominating independent sets // J. Graph Theory. 2019. V. 91, No. 1. P. 88–97.
     
  3. Moon J., Moser L. On cliques in graphs // Israel J. Math. 1965. V. 3, No. 1. P. 23–28.
     
  4. Wood D. R. On the number of maximal independent sets in a graph // Discrete Math. Theor. Comput. Sci. 2011. V. 13, No. 3. P. 17–19.
     
  5. Griggs J., Grinstead C., Guichard D. The number of maximal independent sets in a connected graph // Discrete Math. 1988. V. 68. P. 211–220.
     
  6. Wilf H. The number of maximal independent sets in a tree // SIAM J. Algebr. Discrete Methods. 1986. V. 7, No. 1. P. 125–130.
     
  7. Liu J. Maximal independent sets in bipartite graphs // J. Graph Theory. 1993. V. 17, No. 4. P. 495–507.
     
  8. Hujter M., Tuza Z. The number of maximal independent sets in triangle-free graphs // SIAM J. Discrete Math. 1993. V. 6, No. 2. P. 284–288.
     
  9. Jou M. J., Chang G. Maximal independent sets in graphs with at most one cycle // Discrete Appl. Math. 1997. V. 79. P. 67–73.
     
  10. Ying G. C., Meng K. K., Sagan B. E., Vatter V. E. Maximal independent sets in graphs with at most $r$ cycles // J. Graph Theory. 2006. V. 53, No. 4. P. 270–282.
     
  11. Koh K. M., Goh C. Y., Dong F. M. The maximum number of maximal independent sets in unicyclic connected graphs // Discrete Math. 2008. V. 308, No. 17. P. 3761–3769.
     
  12. Włoch A. On 2-dominating kernels of graphs // Australas. J. Comb. 2012. V. 52. P. 273–284.
     
  13. Bednarz P., Włoch I. On $(2-d)$-kernels in the Cartesian product of graphs // Ann. Univ. Mariae Curie-Skłodowska. Sect. A. 2016. V. 70. P. 1–8.
     
  14. Bednarz P. On $(2-d)$-kernels in the tensor product of graphs // Symmetry. 2021. V. 13. Paper ID 230. 9 p.
     
  15. Bednarz P. On $(2-d)$-kernels in two generalizations of the Petersen graph // Symmetry. 2021. V. 13. Paper ID 1948. 10 p.

Исследование выполнено в Санкт-Петербургском международном математическом институте им. Леонарда Эйлера при финансовой поддержке Министерства науки и высшего образования Российской Федерации (соглашение № 075–15–2022–287).

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

E-mail: dmitalmail@gmail.com

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

Abstract:

A set $J_k$ of graph vertices is said to be $k$-dominating independent $(k \ge 1)$ if its vertices are pairwise adjacent and every vertex not in $J_k$ is adjacent to at least $k$ vertices in $J_k$. In the present paper, we obtain new upper bounds for the number of $k$-dominating independent sets for $k \ge 2$ in some planar graph classes. 
Illustr. 7, bibliogr. 15.

References:
  1. Z. L. Nagy, On the number of $k$-dominating independent sets, J. Graph Theory 84 (4), 566–580 (2017).
     
  2. D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, and M. Vizer, An improvement on the maximum number of $k$-dominating independent sets, J. Graph Theory 91 (1), 88–97 (2019).
     
  3. J. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1), 23–28 (1965).
     
  4. D. R. Wood, On the number of maximal independent sets in a graph, Discrete Math. Theor. Comput. Sci. 13 (3), 17–19 (2011).
     
  5. J. Griggs, C. Grinstead, and D. Guichard, The number of maximal independent sets in a connected graph, Discrete Math. 68, 211–220 (1988).
     
  6. H. Wilf, The number of maximal independent sets in a tree, SIAM J. Algebr. Discrete Methods 7 (1), 125–130 (1986).
     
  7. J. Liu, Maximal independent sets in bipartite graphs, J. Graph Theory 17 (4), 495–507 (1993).
     
  8. M. Hujter and Z. Tuza, The number of maximal independent sets in trianglefree graphs, SIAM J. Discrete Math. 6 (2), 284–288 (1993).
     
  9. M. J. Jou and G. Chang, Maximal independent sets in graphs with at most one cycle, Discrete Appl. Math. 79, 67–73 (1997).
     
  10. G. C. Ying, K. K. Meng, B. E. Sagan, and V. E. Vatter, Maximal independent sets in graphs with at most $r$ cycles, J. Graph Theory 53 (4), 270–282 (2006).
     
  11. K. M. Koh, C. Y. Goh, and F. M. Dong, The maximum number of maximal independent sets in unicyclic connected graphs, Discrete Math. 308 (17), 3761–3769 (2008).
     
  12. A. Włoch, On 2-dominating kernels of graphs, Australas. J. Comb. 52, 273–284 (2012).
     
  13. P. Bednarz and I. Włoch, On $(2-d)$-kernels in the Cartesian product of graphs, Ann. Univ. Mariae Curie-Skłodowska, Sect. A, 70, 1–8 (2016).
     
  14. P. Bednarz, On $(2-d)$-kernels in the tensor product of graphs, Symmetry 13, ID 230 (2021).
     
  15. P. Bednarz, On $(2-d)$-kernels in two generalizations of the Petersen graph, Symmetry 13, ID 1948 (2021).