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 AlQadisiyah^{a},
Udmurt State University^{b}

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. 441452.

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. 312 (in Russian).
 Al' Dzhabri Kh.Sh. The graph of reflexivetransitive relations and the graph of finite topologies, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2015, vol. 25, no. 1, pp. 311 (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. 401409.
 Rodionov V.I. On the number of labeled acyclic digraphs, Discrete Mathematics, 1992, vol. 105, pp. 319321.

Full text

