?
Trees with extremal numbers of k-dominating sets
Discrete Mathematics. 2022. Vol. 345. No. 1. Article 112656.
In this paper we investigate the relation between the number of k-dominating sets and the number of independent sets in a tree. We call the k-interior of a tree T the forest that contains all the vertices of T of degree at least k. Heuberger and Wagner (2008) characterized for all n,d≥3 the n-vertex trees Td,n with maximum vertex degree d and the maximum number of independent sets. We show that for all n,k≥2, if a tree T has the maximum number of k-dominating sets among all n-vertex trees, then either it contains exactly 2⌊n−2k−1⌋ k-dominating sets or its k-interior is isomorphic to a forest aK1∪Tk,b for some integers a,b≥0. Moreover, we completely describe trees with the minimum possible number of k-dominating sets for every k≥2.
Publication based on the results of:
Taletskii D., Математический сборник 2023 Т. 214 № 11 С. 133-156
Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}. ...
Added: November 2, 2023
Taletskii D., Дискретный анализ и исследование операций 2023 Т. 30 № 3 С. 111-131
The set of vertices of a graph is called distance-k independent if the distance between any two of its vertices is greater than some integer k ⩾ 1. In this paper we describe n-vertex trees with a given diameter d which have maximum and minimum possible number of distance-k independent sets among all such trees. The ...
Added: June 13, 2023
D. S. Taletskii, Sbornik Mathematics 2023 Vol. 214 No. 11 P. 1627-1650
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}. ...
Added: March 25, 2024
Taletskii D., / Cornell University. Series arXiv "math". 2023.
We show that the number of independent sets in every outerplanar graph is greater than the number of its 4-dominating sets. ...
Added: May 3, 2023
Taletskii D., Mathematical notes 2021 Vol. 109 P. 280-291
We consider the problem of describing 𝑛-vertex trees of diameter 𝑑 containing as few independent sets as possible. This problem is solved for 𝑑=6 and 𝑛>160, as well as for 𝑑=7 and 𝑛>400. ...
Added: September 20, 2021
Taletskii D., Дискретный анализ и исследование операций 2024 Т. 31 № 1 С. 109-128
The set of graph vertices J_k is called k-dominating independent (k > 1) if its vertices are pairwise adjacent and every vertex not from J_k is adjacent to at least k vertices from J_k. In the presentb paper we obtain new upper bounds for the number of k-dominating independent sets for k > 2 in ...
Added: March 25, 2024
D. S. Taletskii, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 3 P. 664-677
The set of vertices of a graph is called distance-k independent if the distance between any two of its vertices is greater than some integer k ≥ 1. In this paper, we describe n-vertex trees with a given diameter d that have the maximum and minimum possible number of distance-k independent sets among all such ...
Added: November 8, 2023
D. S. Taletskii, Mathematical notes 2023 Vol. 113 P. 552-566
The class of trees in which the degree of each vertex does not exceed an integer 𝑑 is considered. It is shown that, for 𝑑=4, each 𝑛-vertex tree in this class contains at most (√2)^𝑛 minimum dominating sets (MDS), and the structure of trees containing precisely (√2)^𝑛 MDS is described. On the other hand, for 𝑑=5, an 𝑛-vertex tree containing more than (1/3)⋅1.415^𝑛 MDS is ...
Added: April 25, 2023
Taletskii D., Malyshev D., Discrete Mathematics and Applications 2021 Vol. 31 No. 2 P. 135-144
A complete description of trees with maximal possible number of maximum independent setsamong all 𝑛-vertex trees with exactly 𝑙 leaves is obtained. For all values of the parameters 𝑛 and 𝑙, the extremal tree is unique and is the result of merging the endpoints of 𝑙 simple paths. ...
Added: April 13, 2021
Taletskii D., Дискретный анализ и исследование операций 2023 Т. 30 № 1 С. 110-129
The minimum total dominating set (MTDS) of a graph is a vertex subset D of minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of D. In this paper we obtain the sharp upper bound for the number of MTDS in the class of n-vertex 2-caterpillars. We also show that ...
Added: November 15, 2022
D. S. Taletskii, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 213-224
The minimum total dominating set (MTDS) of a graph is a vertex subset D of
minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of D.
In this paper we obtain a sharp upper bound for the number of MTDSs in the class
of n-vertex 2-caterpillars. We also show that for ...
Added: April 25, 2023
Taletskii D., Математические заметки 2023 Т. 113 № 4 С. 577-595
The class of trees in which the degree of each vertex does not exceed an integer d is considered. It is shown that, for d = 4, each n-vertex tree in this class contains at most (√2)^n minimum dominating sets (MDS), and the structure of trees containing precisely (√2)^n MDS is described. On the other hand, ...
Added: April 25, 2023
Taletskii D., Malyshev D., Discrete Applied Mathematics 2022 Vol. 314 P. 321-330
For any n and l, we completely describe trees with the maximum and minimum numbers of maximal independent sets among all n-vertex trees with l leaves. ...
Added: March 30, 2022
Sirotin V., Arkhipova M., Dubrova T. A. et al., Bielsko-Biala : University of Bielsko-Biala Press, 2016
The main attributes of modern enterprises should be the flexibility and the ability of forecasting the future. Constant adaptation to the changing environment and the rapidity of undertaking certain actions which are conditioned by specific situations determine the rules for the future position of market competition. Effective and efficient adjustment of the company in line ...
Added: November 2, 2016
Pahomov F., Известия РАН. Серия математическая 2016 Т. 80 № 6 С. 173-216
Полимодальная логика доказуемости
GLP была введена Г. К. Джапаридзе в 1986 г. Она является логикой доказуемости для ряда цепочек предикатов доказуемости возрастающей силы. Всякой полимодальной логике соответствует многообразие полимодальных алгебр. Л. Д. Беклемишевым и А. Виссером был поставлен вопрос о разрешимости элементарной теории свободной GLP-алгебры, порожденной константами 0, 1 [1]. В этой статье для любого натурального n решается аналогичный вопрос для логик GLPn, являющихся ...
Added: December 4, 2017
Furmanov K. K., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253
Added: December 22, 2016
Buchstaber V., Limonchenko I., / Cornell University. Series math "arxiv.org". 2018. No. 1808.08851.
We introduce the notions of algebraic and geometric direct families of polytopes and develop a theory of such families. The theory is then applied to the problem of existence of nontrivial higher Massey products in cohomology of moment-angle-complexes. ...
Added: September 29, 2019
Shiryaev A., Zhitlukhin M., Ziemba W., / SSRN. Series Social Science Research Network "Social Science Research Network". 2013.
We study the land and stock markets in Japan circa 1990. While the Nikkei stock average in the late 1980s and its -48% crash in 1990 is generally recognized as a financial market bubble, a bigger bubble and crash was in the golf course membership index market. The crash in the Nikkei which started on ...
Added: March 9, 2014
Maslov V., Теоретическая и математическая физика 2019 Т. 201 № 1 С. 65-83
We study the process of a nucleon separating from an atomic nucleus from the mathematical standpoint
using experimental values of the binding energy for the nucleus of the given substance. A nucleon becomes
a boson at the instant of separating from a fermionic nucleus. We study the further transformations of
boson and fermion states of separation in a ...
Added: November 1, 2019
Litvin Y. V., Абрамов И. В., Технологии техносферной безопасности 2016 № 66
Advanced approach to the assessment of a random time of arrival fire fighting calculation on the object of protection, the time of their employment and the free combustion. There is some quantitative assessments with the review of analytical methods and simulation ...
Added: August 27, 2016
Bagrov A. N., Gordin V. A., Bykov P. L., Russian Meteorology and Hydrology 2014 No. 5 P. 283-291
The evaluations of the forecasts of surface air temperature and precipitation for the period July 2010 - June 2013 are presented. The forecasting of surface air temperature at 5 days and precipitation at 3 days are considered. Our complex statistical scheme uses the results of the best foreign global schemes, regional scheme COSMO-RU7. The joint ...
Added: December 7, 2013
Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
Min Namkung, Younghun K., Scientific Reports 2018 Vol. 8 No. 1 P. 16915-1-16915-18
Sequential state discrimination is a strategy for quantum state discrimination of a sender’s quantum
states when N receivers are separately located. In this report, we propose optical designs that can
perform sequential state discrimination of two coherent states. For this purpose, we consider not
only binary phase-shifting-key (BPSK) signals but also general coherent states, with arbitrary prior
probabilities. Since ...
Added: November 16, 2020
Decrouez G. G., Hall P., Bernoulli: a journal of mathematical statistics and probability 2013 Vol. 19 No. 4 P. 1268-1293
Motivated by a problem arising when analysing data from quarantine searches, we explore properties of distributions of sums of independent means of independent lattice-valued random variables. The aim is to determine the extent to which approximations to those sums require continuity corrections. We show that, in cases where there are only two different means, the ...
Added: September 29, 2014