|
This article is cited in 3 scientific papers (total 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.
Received: 01.02.2017
Citation:
Kh. Sh. Al' Dzhabri, V. I. Rodionov, “On support sets of acyclic and transitive digraphs”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 27:2 (2017), 153–161
Linking options:
https://www.mathnet.ru/eng/vuu577 https://www.mathnet.ru/eng/vuu/v27/i2/p153
|
Statistics & downloads: |
Abstract page: | 471 | Full-text PDF : | 152 | References: | 59 |
|