Definability of graphs by congruence lattices
type: Item
instance of: scholarly article
title: Definability of graphs by congruence lattices
zbMATH Open document ID: 0698.05060
DOI: 10.1007/BF01978702
author: N. A. Kulikov
published in: Algebra and Logic
publication date: 1985-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/187300
review text: An undirected graph is an ordered pair \(<G,\tau >\), where G is the vertex set and \(\tau\) is the adjacency relation. The symbol P(G\(\times G)\) denotes the lattice of all subsets of the set \(G\times G\); further, \(C(G)=P(G\times G)\times P(G\times G)\). An element \(\theta =<\theta^ 0,\theta^ 1>\in C(G)\) is a congruence on G if \(\theta^ 0\) is an equivalence relation on G and further \(\tau \subseteq \theta^ 1\) and \(<x,u>\in \theta^ 0\), \(<y,v>\in \theta^ 0\), \(<x,y>\in \theta^ 1\) imply \(<u,v>\in \theta^ 1.\) The symbol \({\mathcal S}\) denotes the quasivariety of undirected graphs without loops. For \(G\in {\mathcal S}\) the congruences \(\theta\) satisfying G/\(\theta\in {\mathcal S}\) form the lattice \(Con_{{\mathcal S}}G\). The symbol \(G^*\) denotes the graph obtained from G by deleting all vertices which are adjacent to all others. Theorem: If G and \(G_ 1\) are incomplete graphs, then \(Con_{{\mathcal S}}G\cong Con_{{\mathcal S}}G_ 1\) if and only if \(G^*\cong G^*_ 1\). A graph G is complete if and only if \(| Con_{{\mathcal S}}G| =2\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4144034
zbMATH Keywords: lattice of all subsets of the set G\(\times G\)
zbMATH Keywords: quasivariety of undirected graphs
MaRDI profile type: Publication
cites work: Q3674739
cites work: Q3875978
description: scientific article; zbMATH DE number 4144034