| Autor: |
Frendrup, Allan, Pedersen, Anders Sune, Sapozhenko, Alexander A., Vestergaard, Preben D. |
| Jazyk: |
angličtina |
| Rok vydání: |
2009 |
| Zdroj: |
Frendrup, A, Pedersen, A S, Sapozhenko, A A & Vestergaard, P D 2009, Merrifield-Simmons index and minimum number of independent sets in shor trees . Research Report Series, no. R-2009-03, Department of Mathematical Sciences, Aalborg University, Aalborg . |
| Popis: |
In 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 ≤ 5. The lower bound is 5 n/3 and we give the structure of the extremal trees. A generalization to connected graphs is stated. In 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 ≤ 5. The lower bound is 5 n/3 and we give the structure of the extremal trees. A generalization to connected graphs is stated. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
