Geodesic
On support sets of acyclic and transitive digraphs
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 2, pp. 153-161 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VUU_2017_27_2_a0,
     author = {Kh. Sh. Al' Dzhabri and V. I. Rodionov},
     title = {On support sets of acyclic and transitive digraphs},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {153--161},
     year = {2017},
     volume = {27},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2017_27_2_a0/}
}
TY  - JOUR
AU  - Kh. Sh. Al' Dzhabri
AU  - V. I. Rodionov
TI  - On support sets of acyclic and transitive digraphs
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2017
SP  - 153
EP  - 161
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VUU_2017_27_2_a0/
LA  - ru
ID  - VUU_2017_27_2_a0
ER  - 
%0 Journal Article
%A Kh. Sh. Al' Dzhabri
%A V. I. Rodionov
%T On support sets of acyclic and transitive digraphs
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2017
%P 153-161
%V 27
%N 2
%U http://geodesic.mathdoc.fr/item/VUU_2017_27_2_a0/
%G ru
%F VUU_2017_27_2_a0
Kh. Sh. Al' Dzhabri; V. I. Rodionov. On support sets of acyclic and transitive digraphs. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 27 (2017) no. 2, pp. 153-161. http://geodesic.mathdoc.fr/item/VUU_2017_27_2_a0/

[1] Al' Dzhabri Kh. Sh., Rodionov V. I., “The graph of partial orders”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, 3–12 (in Russian) | DOI

[2] Al' Dzhabri Kh. Sh., “The graph of reflexive-transitive relations and the graph of finite topologies”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 25:1 (2015), 3–11 (in Russian) | DOI

[3] Al' Dzhabri Kh. Sh., Rodionov V. I., “The graph of acyclic digraphs”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 25:4 (2015), 441–452 (in Russian) | DOI

[4] Comtet L., “Recouvrements, bases de filtre et topologies d'un ensemble fini”, C. R. Acad. Sci., 262 (1966), A1091–A1094 | MR

[5] Erne M., “Struktur- und anzahlformeln fur topologien auf endlichen mengen”, Manuscripta Math., 11:3 (1974), 221–259 | DOI | MR | Zbl

[6] Borevich Z. I., “Enumeration of finite topologies”, J. Sov. Math., 20:6 (1982), 2532–2545 | DOI | Zbl | Zbl

[7] Rodionov V. I., “On enumeration of posets defined on finite set”, Siberian Electronic Mathematical Reports, 13 (2016), 318–330 (in Russian) | DOI | Zbl

[8] Evans J. W., Harary F., Lynn M. S., “On the computer enumeration of finite topologies”, Comm. ACM, 10:5 (1967), 295–297 | DOI | Zbl

[9] Gupta H., “Number of topologies on a finite set”, Research Bulletin of the Panjab University (N.S.), 19 (1968), 231–241 | MR | Zbl

[10] Rodionov V. I., “On the number of labeled acyclic digraphs”, Discrete Mathematics, 105:1–3 (1992), 319–321 | DOI | MR | Zbl

[11] Rodionov V. I., “On recurrence relation in the problem of enumeration of finite posets”, Siberian Electronic Mathematical Reports, 14 (2017), 98–111 (in Russian) | DOI | Zbl

[12] Brinkmann G., McKay B. D., “Posets on up to 16 points”, Order, 19:2 (2002), 147–179 | DOI | MR | Zbl