• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On trees of bounded degree with maximal number of greatest independent sets

Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 2. P. 369-381.
Taletskii D. S., Malyshev D.

For each 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 for all even n an extremal tree is unique but uniqueness may fail for odd n; moreover, for d = 3 and every odd n>6, there are exactly ceil{(n-3)/4} + 1 extremal trees. In the paper, the problem of searching for extremal (n; d)-trees is also considered for 2-caterpillars, i.e., trees in which every vertex lies at distance at most two from some simple path. For each n and d=3,4, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.