On the Number of Connected Sets in Bounded Degree Graphs
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2018
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-19
Series
The Electronic Journal of Combinatorics, Volume 25, issue 4
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.9351n) for d=3, O(1.9812n) for d=4, and O(1.9940n) for d=5. Dually, we construct infinite families of graphs where the number of connected sets is at least Ω(1.7651n) for d=3, Ω(1.8925n) for d=4, and Ω(1.9375n) for d=5.Description
| openaire: EC/H2020/338077/EU//TAPEASE
Keywords
113 Computer and information sciences
Other note
Citation
Kangas , K , Kaski , P , Korhonen , J H & Koivisto , M 2018 , ' On the Number of Connected Sets in Bounded Degree Graphs ' The Electronic Journal of Combinatorics , vol. 25 , no. 4 , P4.34 , pp. 1-19 .