On the number of connected sets in bounded degree graphs

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2018-01-01
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