RUS  ENG
Full version
JOURNALS // Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki // Archive

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2015 Volume 25, Issue 1, Pages 3–11 (Mi vuu459)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024