Geodesic
On the number of connected sets in bounded degree graphs
Kustaa Kangas1 ; Petteri Kaski1 ; Janne H. Korhonen1 ; Mikko Koivisto2
1Department of Computer Science Aalto University
2Department of Computer Science University of Helsinki
The electronic journal of combinatorics, Tome 25 (2018) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $\Omega(1.7651^n)$ for $d=3$, $\Omega(1.8925^n)$ for $d=4$, and $\Omega(1.9375^n)$ for $d=5$.
DOI : 10.37236/7462
Classification : 05C07, 05C30, 05C35, 05C40, 68R10
Mots-clés : connected set, bounded degree graph, Shearer's entropy lemma, computer-assisted proof

Kustaa Kangas  1   ; Petteri Kaski  1   ; Janne H. Korhonen  1   ; Mikko Koivisto  2

1 Department of Computer Science Aalto University
2 Department of Computer Science University of Helsinki 
@article{10_37236_7462,
     author = {Kustaa Kangas and Petteri Kaski and Janne H. Korhonen and Mikko Koivisto},
     title = {On the number of connected sets in bounded degree graphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {4},
     doi = {10.37236/7462},
     zbl = {1402.05039},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7462/}
}
TY  - JOUR
AU  - Kustaa Kangas
AU  - Petteri Kaski
AU  - Janne H. Korhonen
AU  - Mikko Koivisto
TI  - On the number of connected sets in bounded degree graphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7462/
DO  - 10.37236/7462
ID  - 10_37236_7462
ER  - 
%0 Journal Article
%A Kustaa Kangas
%A Petteri Kaski
%A Janne H. Korhonen
%A Mikko Koivisto
%T On the number of connected sets in bounded degree graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7462/
%R 10.37236/7462
%F 10_37236_7462
Kustaa Kangas; Petteri Kaski; Janne H. Korhonen; Mikko Koivisto. On the number of connected sets in bounded degree graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7462

Cité par Sources :