+7 (3412) 91 60 92

## Archive of Issues

Iraq; Russia Al Diwaniyah; Izhevsk
Year
2017
Volume
27
Issue
2
Pages
153-161
 Section Mathematics Title On support sets of acyclic and transitive digraphs Author(-s) Al' Dzhabri Kh.Sh.ab, Rodionov V.I.b Affiliations University of Al-Qadisiyaha, Udmurt State Universityb Abstract In previous works of the authors, the concept of a binary reflexive adjacency relation was introduced on the set of all binary relations of the set $X$, and an algebraic system consisting of all binary relations of the set $X$ and of all unordered pairs of adjacent binary relations was defined. If $X$ is a finite set, then this algebraic system is a graph (graph of binary relations $G$). The current paper introduces the notion of a support set for acyclic and transitive digraphs. This is the collections $S(\sigma)$ and $S'(\sigma)$ consisting of the vertices of the digraph $\sigma\in G$ that have zero indegree and zero outdegree, respectively. It is proved that if $G_\sigma$ is a connected component of the graph $G$ containing the acyclic or transitive digraph $\sigma\in G$, then $\{S(\tau): \tau\in G_\sigma\}=\{S'(\tau): \tau\in G_\sigma\}$. A formula for the number of transitive digraphs having a fixed support set is obtained. An analogous formula for the number of acyclic digraphs having a fixed support set was obtained by the authors earlier. Keywords enumeration of graphs, acyclic digraph, transitive digraph UDC 519.175, 519.115 MSC 05C30 DOI 10.20537/vm170201 Received 1 February 2017 Language Russian Citation Al' Dzhabri Kh.Sh., Rodionov V.I. On support sets of acyclic and transitive digraphs, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2017, vol. 27, issue 2, pp. 153-161. References Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of partial orders, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, issue 4, pp. 3-12 (in Russian). DOI: 10.20537/vm130401 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, issue 1, pp. 3-11 (in Russian). DOI: 10.20537/vm150101 Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of acyclic digraphs, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2015, vol. 25, issue 4, pp. 441-452 (in Russian). DOI: 10.20537/vm150401 Comtet L. Recouvrements, bases de filtre et topologies d'un ensemble fini, C. R. Acad. Sci., 1966, vol. 262, pp. A1091-A1094. Erne M. Struktur- und anzahlformeln fur topologien auf endlichen mengen, Manuscripta Math., 1974, vol. 11, no. 3, pp. 221-259. DOI: 10.1007/BF01173716 Borevich Z.I. Enumeration of finite topologies, J. Sov. Math., 1982, vol. 20, issue 6, pp. 2532-2545. DOI: 10.1007/BF01681470 Rodionov V.I. On enumeration of posets defined on finite set, Siberian Electronic Mathematical Reports, 2016, vol. 13, pp. 318-330 (in Russian). DOI: 10.17377/semi.2016.13.026 Evans J.W., Harary F., Lynn M.S. On the computer enumeration of finite topologies, Comm. ACM, 1967, vol. 10, issue 5, pp. 295-297. DOI: 10.1145/363282.363311 Gupta H. Number of topologies on a finite set, Research Bulletin of the Panjab University (N.S.), 1968, vol. 19, pp. 231-241. Rodionov V.I. On the number of labeled acyclic digraphs, Discrete Mathematics, 1992, vol. 105, no. 1-3, pp. 319-321. DOI: 10.1016/0012-365X(92)90155-9 Rodionov V.I. On recurrence relation in the problem of enumeration of finite posets, Siberian Electronic Mathematical Reports, 2017, vol. 14, pp. 98-111 (in Russian). DOI: 10.17377/semi.2017.14.011 Brinkmann G., McKay B.D. Posets on up to 16 points, Order, 2002, vol. 19, issue 2, pp. 147-179. DOI: 10.1023/A:1016543307592 Full text