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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2023},
     volume = {214},
     number = {11},
     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
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
%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/

[1] H. Prodinger and R. F. Tichy, “Fibonacci numbers of graphs”, Fibonacci Quart., 20:1 (1982), 16–21 | MR | Zbl

[2] C. Heuberger and S. G. Wagner, “Maximizing the number of independent subsets over trees with bounded degree”, J. Graph Theory, 58:1 (2008), 49–68 | DOI | MR | Zbl

[3] N. Alon, “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256 | DOI | MR | Zbl

[4] A. A. Sapozhenko, “Independent sets in quasi-regular graphs”, European J. Combin., 27:7 (2006), 1206–1210 | DOI | MR | Zbl

[5] J. Kahn, “An entropy approach to the hard-core model on bipartite graphs”, Combin. Probab. Comput., 10:3 (2001), 219–238 | DOI | MR | Zbl

[6] Yufei Zhao, “The number of independent sets in a regular graph”, Combin. Probab. Comput., 19:2 (2009), 315–320 | DOI | MR | Zbl

[7] A. B. Dainyak and A. A. Sapozhenko, “Independent sets in graphs”, Discrete Math. Appl., 26:6 (2016), 323–346 | DOI | MR | Zbl

[8] D. Bród and Z. Skupień, “Trees with extremal numbers of dominating sets”, Australas. J. Combin., 35 (2006), 273–290 | MR | Zbl

[9] S. Wagner, “A note on the number of dominating sets of a graph”, Util. Math., 92 (2013), 25–31 | MR | Zbl

[10] D. S. Taletskii, “Trees with extremal numbers of $k$-dominating sets”, Discrete Math., 345:1 (2022), 112656, 5 pp. | DOI | MR | Zbl