Email this article On the number of independent and $k$-dominating sets in graphs with average vertex degree at most $k$
- Authors: Taletskii D.S.1
-
Affiliations:
- National Research University – Higher School of Economics in Nizhny Novgorod
- Issue: Vol 214, No 11 (2023)
- Pages: 133-156
- Section: Articles
- URL: https://journal-vniispk.ru/0368-8666/article/view/147925
- DOI: https://doi.org/10.4213/sm9870
- ID: 147925
Cite item
Open Access
Access granted
Subscription Access
Abstract
The following conjecture is formulated: if the average vertex degree in a graph is not greater than a positive integer k⩾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∈{1,2}.
About the authors
Dmitrii Sergeevich Taletskii
National Research University – Higher School of Economics in Nizhny Novgorod
Author for correspondence.
Email: math-net2025_06@mi-ras.ru
Candidate of physico-mathematical sciences, Scientific Employee
References
- H. Prodinger, R. F. Tichy, “Fibonacci numbers of graphs”, Fibonacci Quart., 20:1 (1982), 16–21
- C. Heuberger, S. G. Wagner, “Maximizing the number of independent subsets over trees with bounded degree”, J. Graph Theory, 58:1 (2008), 49–68
- N. Alon, “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256
- A. A. Sapozhenko, “Independent sets in quasi-regular graphs”, European J. Combin., 27:7 (2006), 1206–1210
- J. Kahn, “An entropy approach to the hard-core model on bipartite graphs”, Combin. Probab. Comput., 10:3 (2001), 219–238
- Yufei Zhao, “The number of independent sets in a regular graph”, Combin. Probab. Comput., 19:2 (2009), 315–320
- А. Б. Дайняк, А. А. Сапоженко, “Независимые множества в графах”, Дискрет. матем., 28:1 (2016), 44–77
- D. Brod, Z. Skupien, “Trees with extremal numbers of dominating sets”, Australas. J. Combin., 35 (2006), 273–290
- S. Wagner, “A note on the number of dominating sets of a graph”, Util. Math., 92 (2013), 25–31
- D. S. Taletskii, “Trees with extremal numbers of $k$-dominating sets”, Discrete Math., 345:1 (2022), 112656, 5 pp.
Supplementary files
