On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets
- Autores: Taletskii D.1, Malyshev D.2,1
-
Afiliações:
- Lobachevsky Nizhny Novgorod State University
- National Research University Higher School of Economics
- Edição: Volume 12, Nº 2 (2018)
- Páginas: 369-381
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213069
- DOI: https://doi.org/10.1134/S1990478918020175
- ID: 213069
Citar
Resumo
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 ≥ 7, there are exactly ⌈(n − 3)/4⌉ + 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 ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.
Palavras-chave
Sobre autores
D. Taletskii
Lobachevsky Nizhny Novgorod State University
Autor responsável pela correspondência
Email: dmitalmail@gmail.com
Rússia, ul. Gagarina 23, Nizhny Novgorod, 603950
D. Malyshev
National Research University Higher School of Economics; Lobachevsky Nizhny Novgorod State University
Email: dmitalmail@gmail.com
Rússia, Bolshaya Pechyorskaya ul. 25/12, Nizhny Novgorod, 603155; ul. Gagarina 23, Nizhny Novgorod, 603950