On the Galois Lattice of Bipartite Distance Hereditary Graphs

DOI10.1007/978-3-319-19315-1_4zbMATH Open1365.05244arXiv1406.0154OpenAlexW2568899965MaRDI QIDQ2946040FDOQ2946040

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)

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.

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

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

zbMATH Keywords

Galois latticePtolemaic graphtransitive reductiondistance hereditary graph

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)

Cites Work

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

Cited In (4)

• On the Galois lattice of bipartite distance hereditary graphs
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• Computing a metric basis of a bipartite distance-hereditary graph
• On computing the Galois lattice of 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)