×

Generating functions of some families of directed uniform hypergraphs. (English. French summary) Zbl 1447.05149

Summary: In this paper, we count acyclic and strongly connected uniform directed labeled hypergraphs. For these combinatorial structures, we introduce a specific generating function allowing us to recover and generalize some results on the number of directed acyclic graphs and the number of strongly connected directed graphs.

MSC:

05C65 Hypergraphs
05A15 Exact enumeration problems, generating functions
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C40 Connectivity
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] K. Archer, I. M. Gessel, C. Graves, and X. Liang. “Counting acyclic and strong digraphs by descents”. 2019.arXiv:1909.01550.
[2] G. Ausiello and L. Luigi. “Directed Hypergraphs: Introduction and fundamental algorithms – a survey”.Theoret. Comput. Sci.658(2017), pp. 293 -306.Link. · Zbl 1356.68159
[3] E. Bender, L. Richmond, R. Robinson, and N. Wormald. “The asymptotic number of acyclic diagraphs I”.Combinatorica6.1 (1986), pp. 15-22.Link. · Zbl 0601.05025
[4] C. Berge.Graphs and Hypergraphs. North-Holland, Amsterdam, 1973. · Zbl 0254.05101
[5] C. Berge.Hypergraphs: Combinatorics of Finite Sets. North-Holland, Amsterdam, 1989. · Zbl 0674.05001
[6] H. Boley. “Directed recursive labelnode hypergraphs: a new representation language”.Artif. Intell.9(1977), pp. 49 -85.Link. · Zbl 0357.68100
[7] E. De Panafieu and S. Dovgal. “Symbolic method and directed graph enumeration”. To appear in the Proceedings of EuroComb2019. 2019.arXiv:1903.09454. · Zbl 1335.05089
[8] P. Flajolet and B. Sedgewick.Analytic Combinatorics. Cambridge University Press, 2009. · Zbl 1165.05001
[9] G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. “Directed hypergraphs and applications”. Discrete Appl. Math.42.2 (1993), pp. 177-201.Link. · Zbl 0771.05074
[10] I. Gessel. “Enumerative applications of a decomposition for graphs and digraphs”.Discrete Math.139.1-3 (1995), pp. 257-271.Link. · Zbl 0827.05045
[11] I. Gessel. “Counting acyclic digraphs by sources and sinks”.Discrete Math.160.1 (1996), pp. 253-258.Link. · Zbl 0863.05042
[12] I. Gessel and B. Sagan. “The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions”.Electr. J. Comb.3.2 (1996).Link. · Zbl 0857.05046
[13] F. Harary, R. Norman, and D. Cartwright.Structural Models: An introduction to the theory of directed graphs. Wiley. New York, 1965. · Zbl 0139.41503
[14] R. Karp. “The Transitive Closure of a Random Digraph”.Random Struct. Algorithms1(1990), pp. 73-94.Link. · Zbl 0712.68076
[15] G. Levi and F. Sirovich. “Generalized And/Or graphs”.Artificial Intelligence7(1976), pp. 243- 259.Link. · Zbl 0333.68063
[16] V. Liskovets. “Enumeration of rooted initially connected oriented graphs”.Izv. Akad. Nauk BSSR(1969), pp. 23-32.
[17] V. Liskovets. “On one recurrent method of counting graphs with marked vertices”.Dokl. Akad. Nauk BSSR184.6 (1969), pp. 1284-1287.
[18] T. Łuczak and T. Seierstad. “The critical behavior of random digraphs”.Random Struct. Algorithms35(2009), pp. 271-293.Link. · Zbl 1214.05157
[19] A. Martelli and U. Montanari. “Additive AND/OR graphs”.Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI). 1973, pp. 1 -11.
[20] J. Ostroff. “Counting Connected Digraphs with Gradings”. Ph.D. thesis. 2013.
[21] D. Ralaivaosaona, V. Rasendrahasina, and S. Wagner. “On the Probability that a Random Digraph is Acyclic”. To appear in the Proceedings of AofA2020. 2020.
[22] R. Read. “The number ofk-colored graphs on labelled nodes”.Canad. J. Math.12(1960).
[23] R. Robinson.Counting labelled acyclic digraphs. New York: Academic Press, 1973. · Zbl 0259.05116
[24] R. Robinson.Counting unlabeled acyclic digraphs. Ed. by C. H. C. Little. Berlin, Heidelberg: Springer Berlin Heidelberg, 1977, pp. 28-43. · Zbl 0376.05031
[25] R. Robinson. “Counting Digraphs with Restrictions on the Strong Components”.Combinatorics and Graph Theory. Vol. 1. Prof. of the Summer School and Conf., 1995.
[26] R. W. Robinson. “Enumeration of acyclic digraphs”.Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970 ). Univ. North Carolina, Chapel Hill, N.C., 1970. · Zbl 0219.05065
[27] R. Stanley. “Acyclic orientations of graphs”.Discrete Math.5.2 (1973), pp. 171 -178.Link. · Zbl 0258.05113
[28] E.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.