On the Galois Lattice of Bipartite Distance Hereditary Graphs

DOI10.1007/978-3-319-19315-1_4MaRDI QIDQ2946040zbMATH OpenOpenAlexFDO

Authors Massimiliano Caramia, Nicola Apollonio, Paolo G. Franciosa

Publication date 15 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distance hereditary graphGalois latticePtolemaic graphtransitive reduction

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Complemented lattices, orthocomplemented lattices and posets (06C15)

Abstract: 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.

Recommendations

• On the Galois lattice of bipartite distance hereditary graphs
• On computing the Galois lattice of bipartite distance hereditary graphs
• Bipartite almost distance-hereditary graphs
• On an extension of distance hereditary graphs
• On an extension of distance-hereditary graphs
• Distance Hereditary Graphs and the Interlace Polynomial
• Powers of distance-hereditary graphs
• scientific article; zbMATH DE number 815104
• Distance-hereditary and strongly distance-hereditary graphs
• An exact enumeration of distance-hereditary graphs

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Crown-free lattices and their related graphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Dismantlable lattices in the mirror
• Distance-hereditary graphs
• scientific article; zbMATH DE number 3681808 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1249514 (Why is no real title available?)
• Lattices with Doubly Irreducible Elements
• On computing the number of linear extensions of a tree
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Restricted unimodular chordal graphs
• Series - parallel graphs and depth-first search trees
• The arborescence-realization problem
• Treelike comparability graphs
• Trees in Concept Lattices

Cited in

(4)

• Computing a metric basis of a bipartite distance-hereditary graph
• On the Galois lattice of bipartite distance hereditary graphs
• On computing the Galois lattice of bipartite distance hereditary graphs
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs

This page was built for publication: On the Galois Lattice of Bipartite Distance Hereditary Graphs

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