Products of graphs with their closed-set lattices

A subset S of the vertex set V(G) of a graph G is called closed, if each vertex of V(G)-S is adjacent to at most one vertex of S. All closed sets in a graph G form a lattice \({\mathcal L}(G)\). A graph G is called minimally (or maximally) critical, if the lattice of closed sets of the graph obtained from G by deleting (or adding respectively) one edge is not isomorphic to \({\mathcal L}(G)\). A graph G is said to be strongly sensitive, if for every graph \(G'\) with \({\mathcal L}(G)\cong {\mathcal L}(G')\) any lattice isomorphism of \({\mathcal L}(G)\) onto \({\mathcal L}(G')\) induces a graph isomorphism of G onto \(G'\). It is proved e.g. that a Cartesian product of any graphs is always maximally critical and is strongly sensitive, if each of its factors is minimally critical.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Products of graphs with their closed-set lattices

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