Archive of Issues
Iraq; Russia Al Diwaniyah; Izhevsk
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 AlQadisiyah^{a}, Udmurt State University^{b} 
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. 153161. 
References 

Full text 