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)
Authors
Kangas, Kustaa
Kaski, Petteri
Korhonen, Janne H.
Koivisto, Mikko
Date
2018-01-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-19
Series
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.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.Description
Keywords
Other note
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