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

Institut for Matematiske Fag

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

3 Citationer (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.

Originalsprog	Engelsk
Tidsskrift	Ars Combinatoria
Vol/bind	111
Sider (fra-til)	85-95
Antal sider	11
ISSN	0381-7032
Status	Udgivet - 2013

Adgang til dokumentet

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

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

Citationsformater

@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

Adgang til dokumentet

AUB Link

Fingeraftryk

Citationsformater