Exploring the Closure Operator for Minimal a, b-Separators: Insights from Galois Connections

Graph algorithms are important for many applications, and studying minimal separators is key to designing efficient graph algorithms. This paper examines minimal a, b-separators in graphs, looking at them from both graph theory and algebraic perspectives, with a focus on lattice theory. It is well known that the set $$\mathscr {M}_{ab}$$ of minimal a, b-separators of a graph forms a complete lattice. Since any lattice is isomorphic to the lattice of closed sets of a closure operator, a natural question arises: from which closure operator and poset can the lattice $$\mathscr {M}_{ab}$$ be obtained? We propose such a closure operator and poset. To this end, we make use of a carefully defined Galois connection. Galois connections naturally appear in lattice theory. To demonstrate our findings, we introduce two types of functions, NC and CN, which form the basis of the closure operator. NC-type functions are closely associated with full components, a concept that frequently appears in graph theoretical studies on minimal a, b-separators. On the other hand, CN-type functions are naturally associated with Galois connections. NC-type and CN-type functions are interrelated, and this interrelation reflects the fusion of graph theoretical and lattice theoretical approaches in this study.