+7 (3412) 91 60 92

## Archive of Issues

Iraq; Russia Al Diwaniyah; Izhevsk
Year
2015
Volume
25
Issue
1
Pages
3-11
 Section Mathematics Title The graph of reflexive-transitive relations and the graph of finite topologies Author(-s) Al' Dzhabri Kh.Sh.ab Affiliations Udmurt State Universitya, University of Al-Qadisiyahb 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 DOI 10.20537/vm150101 Received 12 November 2014 Language Russian Citation Al' Dzhabri Kh.Sh. The graph of reflexive-transitive relations and the graph of finite topologies, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 1, pp. 3-11. References Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of partial orders, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, pp. 3-12 (in Russian). Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsional'nogo analiza (Elements of theory of functions and functional analysis), Moscow: Nauka, 1981, 544 p. Aigner M. Combinatorial theory, Berlin-Heidelberg-New York: Springer-Verlag, 1979, 492 p. Translated under the title Kombinatornaya teoriya, Moscow: Mir, 1982, 558 p. Ore O. Theory of graphs, Providence: Amer. Math. Soc. Colloq. Publ., 1962, vol. 18, 270 p. Translated under the title Teoriya grafov, Moscow: Nauka, 1980, 336 p. Harary F., Palmer E. Graphical enumeration, New York-London: Academic Press, 1973, 272 p. Translated under the title Perechislenie grafov, Moscow: Mir, 1977, 324 p. Comtet L. Recouvrements, bases de filtre et topologies d’un ensemble fini, C. R. Acad. Sci., 1966, vol. AB262, pp. A1091-A1094 (in French). Evans J.W., Harary F., Lynn M.S. On the computer enumeration of finite topologies, Comm. ACM, 1967, vol. 10, pp. 295-297. Gupta H. Number of topologies on a finite set, Res. Bull. Panjab. Univ. (N.S.), 1968, vol. 19, pp. 231-241. Full text