Geodesic
On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$
Sbornik. Mathematics, Tome 214 (2023) no. 11, pp. 1627-1650

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SM_2023_214_11_a4,
     author = {D. S. Taletskii},
     title = {On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$},
     journal = {Sbornik. Mathematics},
     pages = {1627--1650},
     publisher = {mathdoc},
     volume = {214},
     number = {11},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2023_214_11_a4/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$
JO  - Sbornik. Mathematics
PY  - 2023
SP  - 1627
EP  - 1650
VL  - 214
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_2023_214_11_a4/
LA  - en
ID  - SM_2023_214_11_a4
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$
%J Sbornik. Mathematics
%D 2023
%P 1627-1650
%V 214
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_2023_214_11_a4/
%G en
%F SM_2023_214_11_a4
D. S. Taletskii. On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$. Sbornik. Mathematics, Tome 214 (2023) no. 11, pp. 1627-1650. http://geodesic.mathdoc.fr/item/SM_2023_214_11_a4/