|
This article is cited in 3 scientific papers (total in 3 papers)
On trees of bounded degree with maximal number of greatest independent sets
D. S. Taletskiia, D. S. Malyshevba a Lobachevsky Nizhny Novgorod State University, 23 Gagarina Ave., 603950 Nizhny Novgorod, Russia
b National Research University Higher School of Economics, 25/12 Bolshaya Pechyorskaya St., 603155 Nizhny Novgorod, Russia
Abstract:
Given $n$ and $d$, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of $n$-vertex trees of vertex degree at most $d$. We show that the extremal tree is unique for all even $n$ but uniqueness may fail for odd $n$; moreover, for $d=3$ and every odd $n\geq7$, there are exactly $\lceil(n-3)/4\rceil+1$ extremal trees. In the paper, the problem of searching for extremal $(n,d)$-trees is also considered for the $2$-caterpillars; i.e., the trees in which every vertex lies at distance at most $2$ from some simple path. Given $n$ and $d\in\{3,4\}$, we completely reveal all extremal $2$-caterpillars on $n$ vertices each of which has degree at most $d$. Illustr. 9, bibliogr. 10.
Keywords:
extremal combinatorics, tree, greatest independent set.
Received: 29.09.2017
Citation:
D. S. Taletskii, D. S. Malyshev, “On trees of bounded degree with maximal number of greatest independent sets”, Diskretn. Anal. Issled. Oper., 25:2 (2018), 101–123; J. Appl. Industr. Math., 12:2 (2018), 369–381
Linking options:
https://www.mathnet.ru/eng/da898 https://www.mathnet.ru/eng/da/v25/i2/p101
|
Statistics & downloads: |
Abstract page: | 221 | Full-text PDF : | 104 | References: | 23 | First page: | 2 |
|