RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2024 Volume 31, Issue 1, Pages 109–128 (Mi da1341)

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.

UDC: 519.17

Received: 04.05.2023
Revised: 03.07.2023
Accepted: 22.09.2023

DOI: 10.33048/daio.2024.31.770


 English version:
Journal of Applied and Industrial Mathematics, 2024, 18:1, 167–178


© Steklov Math. Inst. of RAS, 2025