Constructions of sensitive graphs which are not strongly sensitive

Let \(G\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). For each \(a\) in \(V(G)\), let \(N(a)=\{x\in V(G): ax\in E(G)\}\) be the set of neighbours of \(a\). A subset \(S\) of \(V(G)\) is called a closed set of \(G\) if, for each pair of distinct elements \(a\), \(b\) in \(S\), \(N(a)\cap N(b)\subseteq S\). Let \({\mathcal L}(G)\) be the family of closed sets of \(G\), inclusive of the empty set \(\emptyset\). Evidently, \({\mathcal L}(G)\) is closed under arbitrary intersection and it thus forms a lattice under set-inclusion. The lattice \({\mathcal L}(G)\), which was first introduced by Sauer, is called the closed-set lattice of the graph \(G\). We shall now introduce, in terms of their closed-set lattices, various classes of graphs. A graph \(G\) is said to be minimally critical if \({\mathcal L}(G)\not\cong{\mathcal L}(G-e)\) for each \(e\) in \(E(G)\), and maximally critical if \({\mathcal L}(G)\not\cong{\mathcal L}(G+e)\) for any \(e\) in \(E(\overline G)\), where \(\overline G\) is the complement of \(G\). We say that \(G\) is critical if \(G\) is both maximally and minimally critical. A graph \(G\) is said to be sensitive if for any graph \(G'\) that \({\mathcal L}(G)\cong{\mathcal L}(G')\) implies \(G\cong G'\). Suppose that \(G\) and \(G'\) are graphs such that \({\mathcal L}(G)\cong{\mathcal L}(G')\) under a lattice isomorphism \(\Phi\). It is easily seen that \(\Phi\) induces naturally a bijection \(\phi: V(G)\to V(G')\) such that for each \(x\) in \(V(G)\), \(\phi(x)=x'\) in \(V(G')\) if and only if \(\Phi(\{x\})=\{x'\}\) in \({\mathcal L}(G')\). We call \(\phi\) the bijection induced by \(\Phi\). A graph \(G\) is said to be strongly sensitive if for any graph \(G'\) and for any lattice isomorphism \(\Phi: {\mathcal L}(G)\cong{\mathcal L}(G')\), the bijection \(\phi\) induced by \(\Phi\) is a graph isomorphism of \(G\) onto \(G'\).

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Constructions of sensitive graphs which are not strongly sensitive

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