Full-text PDF (237 kB) Citations (6)

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.

Received: 12.11.2014

Bibliographic databases:

Citation: Kh. Sh. Al' Dzhabri, “The graph of reflexive-transitive relations and the graph of finite topologies”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 25:1 (2015), 3–11

Citation in format AMSBIB

Linking options:

https://www.mathnet.ru/eng/vuu459

https://www.mathnet.ru/eng/vuu/v25/i1/p3

This publication is cited in the following 6 articles:

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles