On the number of minimal separators in graphs

DOI10.1007/978-3-662-53174-7_9MaRDI QIDQ2827806zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Simon MacKenzie

Publication date 21 October 2016

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

Full work available at URL https://arxiv.org/abs/1503.01203

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Abstract: We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in $O(((1+sqrt5)/2{)}^{n}n)$. We prove that this number is in $omega(1.4521^n)$, improving on the previous best lower bound of $Omega(3^{n/3})subseteqomega(1.4422^n)$. This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.

Recommendations

• On the number of minimal separators in graphs
• Minimal separators in \(P_4\)-sparse graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graphs with polynomially many minimal separators
• scientific article; zbMATH DE number 1420906

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Characterizations and algorithmic applications of chordal graph embeddings
• Combinatorial bounds via measure and conquer
• Efficient enumeration of all minimal separators in a graph
• Exact Algorithms for Treewidth and Minimum Fill-In
• Exact exponential algorithms.
• Finding induced subgraphs via minimal triangulations
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graph theory
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Large Induced Subgraphs via Triangulations and CMSO
• Listing all Minimal Separators of a Graph
• Listing all potential maximal cliques of a graph
• Minimal triangulations of graphs: a survey
• On cliques in graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth computation and extremal combinatorics

Cited in

(13)

• On the number of edges of separated multigraphs
• On the size of minimal separators for treedepth decomposition
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Minimal separators in P₄-tidy graphs
• On the maximum weight minimal separator
• Efficient enumeration of all minimal separators in a graph
• Enumerating Minimal Tropical Connected Sets
• Minimal separators in \(P_4\)-sparse graphs
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• On the number of minimal separators in graphs
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• scientific article; zbMATH DE number 1305094 (Why is no real title available?)

This page was built for publication: On the number of minimal separators in graphs

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