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

Frendrup, Allan; Sune Pedersen , Ander; A.Sapozhenko, Alexander; Vestergaard, Preben Dahl

Abstract

References

Ars Combinatoria

Volume 111
Pages: 85-95

Research article

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

^¹, ^², ^³, ^⁴

¹ Dept. of Mathematics, Aalborg University, Fredrik Bajers Vej 7 G, 9220 Aalborg gst, Denmark

²Dept. of Mathematics & Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark

³Lomonosov University of Moscow Faculty of Computational Mathematics and Cybernetics Leninskie Gory, 119992 Moscow, Russia

⁴ Dept. of Mathematics, Aalborg University, Fredrik Bajers Vej 7 G, 9220 Aalborg gst, Denmark

Published: 31/07/2013

Copyright Link
License

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.

Contents

Ars Combinatoria

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

Abstract

Information

Guidelines

CP Initiatives

Follow CP