Learning Centre

On the number of connected sets in bounded degree graphs

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Kangas, Kustaa
dc.contributor.author Kaski, Petteri
dc.contributor.author Korhonen, Janne H.
dc.contributor.author Koivisto, Mikko
dc.date.accessioned 2019-03-05T10:14:40Z
dc.date.available 2019-03-05T10:14:40Z
dc.date.issued 2018-01-01
dc.identifier.citation Kangas , K , Kaski , P , Korhonen , J H & Koivisto , M 2018 , ' On the number of connected sets in bounded degree graphs ' , Electronic Journal of Combinatorics , vol. 25 , no. 4 , #P4.34 , pp. 1-19 . https://doi.org/10.37236/7462 en
dc.identifier.issn 1077-8926
dc.identifier.other PURE UUID: 43610bfd-7998-4e30-b86b-41a88e91a967
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/43610bfd-7998-4e30-b86b-41a88e91a967
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85061616265&partnerID=8YFLogxK
dc.identifier.other PURE LINK: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p34
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/32268434/7462_PDF_file_26164_3_10_20181115.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/37011
dc.description.abstract A set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer’s entropy lemma and a computer search, we show that the number of connected sets in a graph with n vertices and maximum vertex degree d is at most O(1.9351 n ) for d = 3, O(1.9812 n ) for d = 4, and O(1.9940 n ) for d = 5. Dually, we construct infinite families of graphs where the number of connected sets is at least Ω(1.7651 n ) for d = 3, Ω(1.8925 n ) for d = 4, and Ω(1.9375 n ) for d = 5. en
dc.format.extent 1-19
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Electronic Journal of Combinatorics
dc.relation info:eu-repo/grantAgreement/EC/H2020/338077/EU//TAPEASE
dc.relation.ispartofseries Electronic Journal of Combinatorics en
dc.relation.ispartofseries Volume 25, issue 4 en
dc.rights openAccess en
dc.title On the number of connected sets in bounded degree graphs en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.contributor.department University of Helsinki
dc.identifier.urn URN:NBN:fi:aalto-201903052157
dc.identifier.doi 10.37236/7462
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication