RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2023 Volume 214, Number 11, Pages 133–156 (Mi sm9870)

On the number of independent and $k$-dominating sets in graphs with average vertex degree at most $k$

D. S. Taletskii

Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia

Abstract: The following conjecture is formulated: if the average vertex degree in a graph is not greater than a positive integer $k \geqslant 1$, then the number of $k$-dominating sets in this graph does not exceed the number of its independent sets, and these numbers are equal to each other if and only if the graph is $k$-regular. This conjecture is proved for $k \in \{1,2\}$.
Bibliography: 10 titles.

Keywords: independent set, dominating set, $k$-dominating set, enumerative combinatorics.

MSC: 05C30

Received: 22.12.2022 and 20.06.2023

DOI: 10.4213/sm9870


 English version:
Sbornik: Mathematics, 2023, 214:11, 1627–1650

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025