Volume 25, No 2, 2018, P. 101-123

UDC 519.17
D. S. Taletskii and D. S. Malyshev
On trees of bounded degree with maximal number of greatest independent sets

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 \ge 7$, there are exactly $\left \lceil \dfrac{n - 3}{4} \right \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.

DOI: 10.17377/daio.2018.25.591

Dmitry S. Taletskii ¹
Dmitry S. Malyshev ^2,1
1. Lobachevsky Nizhny Novgorod State University,
23 Gagarina Ave., 603950 Nizhny Novgorod, Russia
2. National Research University Higher School of Economics,
25/12 Bolshaya Pechyorskaya St., 603155 Nizhny Novgorod, Russia
e-mail: dmitalmail@gmail.com, dsmalyshev@rambler.ru

Received 29 September 2017

References

[1] E. Andriantiana, Energy, Hosoya index and Merrifield–Simmons index of trees with prescribed degree sequence, Discrete Appl. Math., 161, No. 6, 724–741, 2013.

[2] J. Griggs, C. Grinstead, and D. Guichard, The number of maximal independent sets in a connected graph, Discrete Math., 68, No. 2–3, 211–220, 1988.

[3] C. Heuberger and S. Wagner, Maximizing the number of independent subsets over trees with bounded degree, J. Graph Theory, 58, No. 1, 49–68, 2007.

[4] M. Hujter and Z. Tuza, The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math., 6, No. 2, 284–288, 1993.

[5] M. Jou and G. Chang, Maximal independent sets in graphs with at most one cycle, Discrete Appl. Math., 79, No. 1–3, 67–73, 1997.

[6] M. Jou and G. Chang, The number of maximum independent sets in graphs, J. Graph Theory, 4, No. 4, 685–695, 2000.

[7] J. Liu, Maximal independent sets in bipartite graphs, J. Graph Theory, 17, No. 4, 495–507, 1993.

[8] J. Moon and L. Moser, On cliques in graphs, Isr. J. Math., 3, 23–28, 1965.

[9] H. Wilf, The number of maximal independent sets in a tree, SIAM J. Algebraic Discrete Methods, 7, No. 1, 125–130, 1986.

[10] J. Zito, The structure and maximum number of maximum independent sets in trees, J. Graph Theory, 15, No. 2, 207–221, 1991.