phone +7 (3412) 91 60 92

Archive of Issues

Iraq; Russia Al Diwaniyah; Izhevsk
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.
  1. 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).
  2. 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).
  3. 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.
  4. Rodionov V.I. On the number of labeled acyclic digraphs, Discrete Mathematics, 1992, vol. 105, pp. 319-321.
Full text
Next article >>