On an isomorphism problem on the closed-set lattice of a graph

In an undirected graph G with the vertex set V(G) the symbol N(a) denotes the set of vertices which are adjacent to a vertex a. A subset S of V(G) is called closed, if \(N(a)\cap N(b)\subseteq S\) for any two distinct vertices a, b of S. Among closed sets of G there are also the empty set and all one-element subsets of V(G). All closed sets of G form the lattice \({\mathcal L}(G)\). If a graph G has the property that \({\mathcal L}(G)\cong {\mathcal L}(G')\) implies \(G\cong G'\) for every graph G', it is called sensitive. A lattice isomorphism \(\phi\) of \({\mathcal L}(G)\) onto \({\mathcal L}(G')\) induces the bijection \(\phi\) of V(G) onto V(G') such that \(\phi (x)=x'\) if and only if \(\Phi (\{x\})=\{x'\}.\) If for every graph G' such that \({\mathcal L}(G)\cong {\mathcal L}(G')\) and for each lattice isomorphism \(\Phi\) of \({\mathcal L}(G)\) onto \({\mathcal L}(G')\) the mapping \(\phi\) induced by \(\Phi\) is a graph isomorphism of G onto G', then G is said to be strongly sensitive. The covering graph of a lattice L is the graph whose vertex set is L and in which two vertices are adjacent if and only if one of them covers the other in L. Strongly sensitive graphs are characterized. It is proved that all graphs without circuits of the length 4 and all covering graphs of lattices are strongly sensitive.

Recommendations

Cited in

(10)

This page was built for publication: On an isomorphism problem on the closed-set lattice of a graph

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