Contents

Ars Combinatoria

  • Research article

Merrifield-Simmons index and minimum Number of Independent Sets in Short Trees

Allan Frendrup1, Ander Sune Pedersen 2, Alexander A.Sapozhenko3, Preben Dahl Vestergaard4
1 Dept. of Mathematics, Aalborg University, Fredrik Bajers Vej 7 G, 9220 Aalborg gst, Denmark
2Dept. of Mathematics & Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark
3Lomonosov University of Moscow Faculty of Computational Mathematics and Cybernetics Leninskie Gory, 119992 Moscow, Russia
4 Dept. of Mathematics, Aalborg University, Fredrik Bajers Vej 7 G, 9220 Aalborg gst, Denmark
  • Published: 31/07/2013

Abstract

In \textit{Ars Comb.} \({84} (2007), 85-96\), Pedersen and Vestergaard posed the problem of determining a lower bound for the number of independent sets in a tree of fixed order and diameter \(d\). Asymptotically, we give here a complete solution for trees of diameter \(d \leq 5\). The lower bound is \(5^{\frac{n}{3}}\) and we give the structure of the extremal trees. A generalization to connected graphs is stated.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Allan Frendrup, Ander Sune Pedersen , Alexander A.Sapozhenko, Preben Dahl Vestergaard. Merrifield-Simmons index and minimum Number of Independent Sets in Short Trees[J], Ars Combinatoria, Volume 111. 85-95. .