+7 (3412) 91 60 92

## Archive of Issues

Iraq; Russia Al Diwaniyah; Izhevsk
Year
2015
Volume
25
Issue
4
Pages
441-452
 Section Mathematics Title The graph of acyclic digraphs Author(-s) Al' Dzhabri Kh.Sh.ab, Rodionov V.I.b Affiliations University of Al-Qadisiyaha, Udmurt State Universityb Abstract The paper introduces the concept of a binary reflexive relation of adjacency on the set of all binary relations of a set $X$ (in terms of characteristic functions) and determines an algebraic system consisting of all binary relations of the set and of all unordered pairs of adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs”). It is proved that the diameter of a graph of binary relations is 2. It is shown that if $\sigma$ and $\tau$ are adjacent relations, then $\sigma$ is an acyclic relation (finite acyclic digraph) if and only if $\tau$ is an acyclic relation. An explicit formula for the number of connected components of a graph of acyclic relations is received Keywords binary relation, acyclic digraph UDC 519.175, 519.115 MSC 05C30 DOI 10.20537/vm150401 Received 23 October 2015 Language Russian Citation Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of acyclic digraphs, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 4, pp. 441-452. 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). Al' Dzhabri Kh.Sh. The graph of reflexive-transitive relations and the graph of finite topologies, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2015, vol. 25, no. 1, pp. 3-11 (in Russian). Liskovets V.A. On the number of maximal vertices of a random acyclic digraph, Theory Probab. Appl., 1976, vol. 20, no. 2, pp. 401-409. Rodionov V.I. On the number of labeled acyclic digraphs, Discrete Mathematics, 1992, vol. 105, pp. 319-321. Full text