This article is cited in
6 papers
MATHEMATICS
The graph of reflexive-transitive relations and the graph of finite topologies
Kh. Sh. Al' Dzhabriab a Udmurt State University, ul. Universitetskaya, 1, Izhevsk, 426034, Russia
b University of Al-Qadisiyah, ul. Babilon, 29, Al Diwaniyah, Iraq
Abstract:
Any binary relation
$\sigma\subseteq X^2$ (where
$X$ is an arbitrary set) generates on the set
$X^2$ a characteristic function: if
$(x,y)\in\sigma$, then
$\sigma(x,y)=1$, otherwise
$\sigma(x,y)=0$. In terms of characteristic functions we introduce on the set of all binary relations of the set
$X$ the concept of a binary reflexive relation of adjacency and determine an algebraic system consisting of all binary relations of the set and of all unordered pairs of various adjacent binary relations. If
$X$ is a finite set then this algebraic system is a graph (“the graph of graphs”).
It is shown that if
$\sigma$ and
$\tau$ are adjacent relations then
$\sigma$ is a reflexive-transitive relation if and only if
$\tau$ is a reflexive-transitive relation. Several structure features of the graph
$G(X)$ of reflexive-transitive relations are investigated. In particular, if
$X$ consists of
$n$ elements, and
$T_0(n)$ is the number of labeled
$T_0$-topologies defined on the set
$X$, then the number of connected components is equal to
$\sum_{m=1}^nS(n,m)T_0(m-1)$, where
$S(n,m)$ are Stirling numbers of second kind. (It is well known that the number of vertices in a graph
$G(X)$ is equal to
$\sum_{m=1}^nS(n,m)T_0(m)$.)
Keywords:
graph, reflexive-transitive relation, finite topology.
UDC:
519.175+519.115.5
MSC: 05C30 Received: 12.11.2014