RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2018 Volume 25, Issue 2, Pages 101–123 (Mi da898)

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


 English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 369–381

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024