This article is cited in
3 papers
MATHEMATICS
On support sets of acyclic and transitive digraphs
Kh. Sh. Al' Dzhabria,
V. I. Rodionovb a University of Al-Qadisiyah, ul. Babilon, 29, Al Diwaniyah, Iraq
b Udmurt State University,
ul. Universitetskaya, 1, Izhevsk, 426034, Russia
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 Received: 01.02.2017
DOI:
10.20537/vm170201