2014/06/01 by Nicola Apollonio, Apollonio, Nicola, Massimiliano Caramia +3
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Rough Sets and Fuzzy Logic #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1406.0154
arxiv created 2014/06/01 · openalex publication_date 2014/06/01 · arxiv updated 2014/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a Bipartite Distance Hereditary graph. By relying on the interplay between bipartite distance hereditary graphs and series-parallel graphs, we show that the lattice can be realized as the containment relation among directed paths in an arborescence. Moreover, a compact encoding of Bipartite Distance Hereditary graphs is proposed, that allows optimal time computation of neighborhood intersections and maximal bicliques.