Products of graphs with their closed-set lattices

Abstract

Let L(G), V(G) and Ḡ be, respectively, the closed-set lattice, vertex set, edge set and complement of a graph G. Any lattice isomorphism Φ:L(G){reversed tilde equals}L(G′) induces a bijection Φ:V(G)→V(G′) such that for each x in V(G),Φ(x)=x′ iff Φ({x})={x′}. A graph G is strongly sensitive if for any graph G′ and any lattice isomorphism Φ:L(G){reversed tilde equals}L(G′), the bijection Φ induced by Φ is a graph isomorphism of G onto G′. G is minimally critical if L(G) ∥ L(G-e) for each e in E(G), and maximally critical if L(G) ∥ L(G+e) for any e in E( G ̌). In this paper, we prove that for any two nontrivial graphs G1 and G2, (1) G1 × G2 is maximally critical, and (2) G1 × G2 is strongly sensitive iff G1 × G2 is minimally critical. Necessary and sufficient conditions on G1 such that G1 × G2 is strongly sensitive are also obtained. © 1988.