arXiv Analytics

Sign in

arXiv:1406.0154 [cs.DM]AbstractReferencesReviewsResources

On the Galois Lattice of Bipartite Distance Hereditary Graphs

Nicola Apollonio, Massimiliano Caramia, Paolo Giulio Franciosa

Published 2014-06-01Version 1

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.

Related articles: Most relevant | Search more
arXiv:1102.1138 [cs.DM] (Published 2011-02-06, updated 2011-02-09)
Critical Sets in Bipartite Graphs
arXiv:1612.07113 [cs.DM] (Published 2016-12-21)
Readability of digraphs and bipartite graphs
arXiv:1107.4711 [cs.DM] (Published 2011-07-23)
Finding All Allowed Edges in a Bipartite Graph