On the Number of Connected Sets in Bounded Degree Graphs

DOI10.1007/978-3-319-12340-0_28zbMath1417.05101OpenAlexW2279593527MaRDI QIDQ2945202

Janne H. Korhonen, Mikko Koivisto, Kustaa Kangas, Petteri Kaski

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10138/293032

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Vertex degrees (05C07)

Related Items

On the number of connected sets in bounded degree graphs ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• An upper bound for the number of independent sets in regular graphs
• Some intersection theorems for ordered sets and graphs
• Independent sets in regular graphs and sum-free subsets of finite groups
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Trimmed Moebius inversion and graphs of bounded degree
• Treewidth computation and extremal combinatorics
• On independent sets and bicliques in graphs
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Finding Induced Subgraphs via Minimal Triangulations
• The traveling salesman problem in bounded degree graphs
• The Number of Independent Sets in a Regular Graph
• Feedback Vertex Sets in Tournaments
• Combinatorial bounds via measure and conquer
• On cliques in graphs