|
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
|
|
+7 (3412) 91 60 92
Russian