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. Relations with the class of Ptolemaic graphs are discussed and exploited to give an alternative proof of the result.
On the Galois Lattice of Bipartite Distance Hereditary Graphs / Apollonio, Nicola; M., Caramia; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 190-191:(2015), pp. 13-23. [10.1016/j.dam.2015.03.014]
On the Galois Lattice of Bipartite Distance Hereditary Graphs
APOLLONIO, Nicola;FRANCIOSA, Paolo Giulio
2015
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. Relations with the class of Ptolemaic graphs are discussed and exploited to give an alternative proof of the result.File | Dimensione | Formato | |
---|---|---|---|
Apollonio_Galois-lattice_2015.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
480.35 kB
Formato
Adobe PDF
|
480.35 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.