On the Number of Connected Sets in Bounded Degree Graphs

DOI10.1007/978-3-319-12340-0_28MaRDI QIDQ2945202zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• On the number of connected sets in bounded degree graphs
• Bounds on the connected domination number of a graph
• Bounds on the connected \(k\)-domination number in graphs
• On the number of connected sets with the neighborhood of a given size in a graph
• scientific article; zbMATH DE number 1792666
• The number and average size of connected sets in graphs with degree constraints
• scientific article; zbMATH DE number 4160792
• On the number of connected subgraphs of graphs
• scientific article; zbMATH DE number 165528
• scientific article; zbMATH DE number 4035879

Cites work

• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• An entropy approach to the hard-core model on bipartite graphs
• An upper bound for the number of independent sets in regular graphs
• Combinatorial bounds via measure and conquer
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Feedback vertex sets in tournaments
• Finding induced subgraphs via minimal triangulations
• Finding optimal Bayesian network given a super-structure
• Independent sets in regular graphs and sum-free subsets of finite groups
• On cliques in graphs
• On independent sets and bicliques in graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Some intersection theorems for ordered sets and graphs
• The number of independent sets in a regular graph
• The traveling salesman problem in bounded degree graphs
• Treewidth computation and extremal combinatorics
• Trimmed Moebius inversion and graphs of bounded degree

Cited in

(11)

• The number and average size of connected sets in graphs with degree constraints
• Extremal problems for connected set enumeration
• On the asymptotics of degree structure of configuration graphs with bounded number of edges
• Bounded-degree graphs can have arbitrarily large slope numbers
• On the number of connected sets with the neighborhood of a given size in a graph
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• On the number of connected subgraphs with small edge‐boundary in regular graphs
• scientific article; zbMATH DE number 4160792 (Why is no real title available?)
• scientific article; zbMATH DE number 3920519 (Why is no real title available?)
• On the number of connected sets in bounded degree graphs
• Irreversible 2-conversion set in graphs of bounded degree

This page was built for publication: On the Number of Connected Sets in Bounded Degree Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945202)