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.
Apollonio, N., Caramia, M., Franciosa, P. (2015). On the Galois lattice of bipartite distance hereditary graphs. DISCRETE APPLIED MATHEMATICS, 190-191, 13-23 [10.1016/j.dam.2015.03.014].
On the Galois lattice of bipartite distance hereditary graphs
CARAMIA, MASSIMILIANO;
2015-01-01
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 in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
DAM_2015.pdf
solo utenti autorizzati
Licenza:
Copyright dell'editore
Dimensione
488.93 kB
Formato
Adobe PDF
|
488.93 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
