Merrifield-simmons index and minimum number of independent sets in short trees

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

Merrifield-simmons index and minimum number of independent sets in short trees

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

Department of Mathematical Sciences

Research output: Contribution to journal › Journal article › Research › peer-review

3 Citations (Scopus)

Abstract

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 s tated.

Original language	English
Journal	Ars Combinatoria
Volume	111
Pages (from-to)	85-95
Number of pages	11
ISSN	0381-7032
Publication status	Published - 2013

Access to Document

http://www.scopus.com/inward/record.url?scp=84902583770&partnerID=8YFLogxK

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@article{7dab3b29be0546fa85522bc8095f1748,

title = "Merrifield-simmons index and minimum number of independent sets in short trees",

abstract = "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 5n/3 and we give the structure of the extremal trees. A generalization to connected graphs is s tated.",

author = "Allan Frendrup and Pedersen, {Anders Sune} and Sapozhenko, {Alexander A.} and Vestergaard, {Preben Dahl}",

year = "2013",

language = "English",

volume = "111",

pages = "85--95",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Merrifield-simmons index and minimum number of independent sets in short trees

AU - Frendrup, Allan

AU - Pedersen, Anders Sune

AU - Sapozhenko, Alexander A.

AU - Vestergaard, Preben Dahl

PY - 2013

Y1 - 2013

N2 - 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 5n/3 and we give the structure of the extremal trees. A generalization to connected graphs is s tated.

AB - 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 5n/3 and we give the structure of the extremal trees. A generalization to connected graphs is s tated.

M3 - Journal article

AN - SCOPUS:84902583770

SN - 0381-7032

VL - 111

SP - 85

EP - 95

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -

Merrifield-simmons index and minimum number of independent sets in short trees

Abstract

Access to Document

AUB Link

Fingerprint

Cite this