On the number of connected sets in bounded degree graphs (Q1627210)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the number of connected sets in bounded degree graphs |
scientific article |
Statements
On the number of connected sets in bounded degree graphs (English)
0 references
22 November 2018
0 references
Summary: A set of vertices in a graph is \textit{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\).
0 references
connected set
0 references
bounded degree graph
0 references
Shearer's entropy lemma
0 references
computer-assisted proof
0 references
0 references