On the number of connected sets in bounded degree graphs
type: Item
instance of: scholarly article
title: On the number of connected sets in bounded degree graphs
zbMATH Open document ID: 1402.05039
author: Kustaa Kangas
author: Petteri Kaski
author: Janne H. Korhonen
author: Mikko Koivisto
published in: The Electronic Journal of Combinatorics
publication date: 2018-11-22T00:00:00Z
full work available at URL: v25i4p34
review text: 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\).
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6983032
zbMATH Keywords: connected set
zbMATH Keywords: bounded degree graph
zbMATH Keywords: Shearer's entropy lemma
zbMATH Keywords: computer-assisted proof
MaRDI profile type: Publication
cites work: Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
cites work: Independent sets in regular graphs and sum-free subsets of finite groups
cites work: Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
cites work: Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
cites work: Trimmed Moebius inversion and graphs of bounded degree
cites work: The traveling salesman problem in bounded degree graphs
cites work: Q5393667
cites work: On the number of maximal bipartite subgraphs of a graph
cites work: Some intersection theorems for ordered sets and graphs
cites work: On the minimum feedback vertex set problem: Exact and enumeration algorithms
cites work: Combinatorial bounds via measure and conquer
cites work: Finding Induced Subgraphs via Minimal Triangulations
cites work: An upper bound for the number of independent sets in regular graphs
cites work: On independent sets and bicliques in graphs
cites work: On the number of minimal separators in graphs
cites work: Feedback Vertex Sets in Tournaments
cites work: Enumerating minimal connected dominating sets in graphs of bounded chordality
cites work: Enumeration and maximum number of minimal connected vertex covers in graphs
cites work: Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
cites work: An entropy approach to the hard-core model on bipartite graphs
cites work: On the Number of Connected Sets in Bounded Degree Graphs
cites work: Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
cites work: On cliques in graphs
cites work: Q3096193
cites work: Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
cites work: Q4595189
cites work: The Number of Independent Sets in a Regular Graph
description: scientific article; zbMATH DE number 6983032