On an isomorphism problem on the closed-set lattice of a graph
type: Item
instance of: scholarly article
title: On an isomorphism problem on the closed-set lattice of a graph
zbMATH Open document ID: 0556.05059
DOI: 10.1007/BF00383605
author: K. S. Poh
author: K. M. Koh
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 06B99
zbMATH DE Number: 3885966
zbMATH Keywords: closed-set lattice of a graph
zbMATH Keywords: covering graph of a poset
zbMATH Keywords: covering graph of a lattice
zbMATH Keywords: Strongly sensitive graphs
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00383605
OpenAlex ID: W2051370137
Recommended article: Q3695305
Recommended article: On the Lattice Isomorphism Problem
Recommended article: The isomorphism problem for classes of graphs closed under contraction
Recommended article: On lattices determined up to isomorphisms by their graphs
Recommended article: Q4710599
Recommended article: Q4017160
Recommended article: Q4294604
Recommended article: Q3703937
Recommended article: On the isomorphism problem for finite Cayley graphs of bounded valency
Recommended article: Q3325059
description: scientific article; zbMATH DE number 3885966