This article is cited 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.
UDC:
519.17 Received: 29.09.2017
DOI:
10.17377/daio.2018.25.591