|
On the number of $k$-dominating independent sets in planar graphs
D. S. Taletskiiab a National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
b Saint Petersburg State University, 7/9 Universitetskaya Embankment, 199034 Saint Petersburg, Russia
Abstract:
A set $J_k$ of graph vertices is said to be $k$-dominating independent ($k \geq 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 \geq 2$ in some planar graph classes. Illustr. 7, bibliogr. 15.
Keywords:
independent set, dominating set, $k$-dominating independent set, planar graph.
Received: 04.05.2023 Revised: 03.07.2023 Accepted: 22.09.2023
Citation:
D. S. Taletskii, “On the number of $k$-dominating independent sets in planar graphs”, Diskretn. Anal. Issled. Oper., 31:1 (2024), 109–128; J. Appl. Industr. Math., 18:1 (2024), 167–178
Linking options:
https://www.mathnet.ru/eng/da1341 https://www.mathnet.ru/eng/da/v31/i1/p109
|
Statistics & downloads: |
Abstract page: | 45 | Full-text PDF : | 1 | References: | 16 | First page: | 5 |
|