Separability generalizes Dirac's theorem
A set of vertices in a graph is a maximal clique module if it is a module (a homogeneous set) and a clique, and is inclusion-maximal with respect to both properties. A maximal clique module of a graph \(G\) is called a moplex if its neighborhood is a minimal separator of \(G\). A moplex is simplicial if its neighborhood is a clique. The authors prove: (1) Every incomplete (triangulated) graph has at least two nonadjacent (simplicial) moplexes. (2) On every graph, the lexicographic breadth-first-search ends at a vertex belonging to a moplex. Since in a triangulated graph every vertex of a moplex is a simplicial vertex, (1) generalizes a well-known theorem of \textit{G. A. Dirac} [On rigid circuit graphs, Abh. Math. Semin. Univ. Hamb. 25, 71-76 (1961)] saying that every incomplete triangulated graph has at least two nonadjacent simplicial vertices. (2) implies that a moplex in a graph can be found in linear time.
- Algorithmic Aspects of Vertex Elimination on Graphs
- Decomposition by clique separators
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- scientific article; zbMATH DE number 3338381 (Why is no real title available?)
- Incidence matrices and interval graphs
- Meyniel weakly triangulated graphs. II: A theorem of Dirac
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- On rigid circuit graphs
- On the semi-perfect elimination
- Perfect Elimination and Chordal Bipartite Graphs
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Some aspects of perfect elimination orderings in chordal graphs
- Minimal interval completion through graph exploration
- Meyniel weakly triangulated graphs. II: A theorem of Dirac
- Graph extremities defined by search algorithms
- Computing a clique tree with the algorithm maximal label search
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Representing a concept lattice by a graph
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Graph searches and their end vertices
- Avoidable paths in graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Robinsonian matrices: recognition challenges
- Moplex orderings generated by the LexDFs algorithm
- Vertex elimination orderings for hereditary graph classes
- Junction trees of general graphs
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Moplex elimination orderings
- Extremities and orderings defined by generalized graph search algorithms
- Organizing the atoms of the clique separator decomposition into an atom tree
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- The separability ‘‘theorem’’ in terms of distributions with discussion of electromagnetic scattering theory
- Separator orders in interval, cocomparability, and AT-free graphs
- Asteroidal triples of moplexes
- Shifting paths to avoidable ones
- Computing and listing avoidable vertices and paths
- Finding biclique partitions of co-chordal graphs
- Computing and listing avoidable vertices and paths
- Bisimplicial separators
- Graphs with at most two moplexes
- On minimally t-tough graphs with t 1
- Growing trees and amoebas' replications
- Obstructions to faster diameter computation: asteroidal sets
- Avoidability beyond paths
- Clustering analysis of a dissimilarity: a review of algebraic and geometric representation
- Minimal triangulations of graphs: a survey
- Minimal proper interval completions
This page was built for publication: Separability generalizes Dirac's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392561)
