×

Counting acyclic and strong digraphs by descents. (English) Zbl 1452.05073

In this paper, the authors refine the counting formulas for four classes of labeled directed graphs with \(n\) nodes and \(m\) edges by additional accounting for the number of descents. Hereby, a descent is a directed edge \((s,t)\) with \(s > t\). The considered classes are strongly connected tournaments, strongly connected directed graphs, acyclic directed graphs, and forests (or trees). Their method builds on the known recursive formulas for these classes which are enriched by the number of descents. Then, they use special types of generating functions, such as Eulerian generating functions and a new variant developed by them called graphic Eulerian generating function, to derive closed forms or functional equations.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Drake, B., An Inversion Theorem for Labeled Trees and Some Limits of Areas under Lattice Paths (2008), Brandeis University, (Ph.D. thesis)
[2] Eğecioğlu, Ö.; Remmel, J. B., Bijections for Cayley trees, spanning trees, and their \(q\)-analogues, J. Combin. Theory Ser. A, 42, 15-30 (1986) · Zbl 0595.05025
[3] Gessel, I. M., A \(q\)-analog of the exponential formula, Discrete Math., 40, 69-80 (1982) · Zbl 0485.05004
[4] Gessel, I. M., Enumerative applications of a decomposition for graphs and digraphs, Discrete Math., 139, 257-271 (1995) · Zbl 0827.05045
[5] Gessel, I. M., Counting acyclic digraphs by sources and sinks, Discrete Math., 160, 253-258 (1996) · Zbl 0863.05042
[6] Gessel, I., Counting forests by descents and leaves, The Foata Festschrift, Electron. J. Combin., 3, 2 (1996), Research Paper 8, 5 pp
[7] Gessel, I. M., Lagrange inversion, J. Combin. Theory Ser. A, 144, 212-249 (2016) · Zbl 1343.05021
[8] Gessel, I. M.; Sagan, B. E., The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, The Foata Festschrift, Electron. J. Combin., 3, 2 (1996), Research Paper 9, 36 pp. · Zbl 0857.05046
[9] Gessel, I. M.; Seo, S., A refinement of Cayley’s formula for trees, Electron. J. Combin., 11, 2 (2004), Research Paper 27, 23 pp
[10] Liskovec, V. A., A recurrent method for the enumeration of graphs with labelled vertices (Russian), Dokl. Akad. Nauk SSSR, 184, 1284-1287 (1969), English translation in Soviet Math. Dokl. 10 (1969) 242-246
[11] Moon, J. W.; Moser, L., Almost all tournaments are irreducible, Canad. Math. Bull., 5, 61-65 (1962) · Zbl 0105.33304
[12] Ostroff, J., Counting Connected Digraphs with Gradings (2013), Brandeis University, (Ph.D. Thesis)
[13] de Panafieu, É.; Dovgal, S., Symbolic method and directed graph enumeration, Acta Math. Univ. Comen. (N.S.), 88, 3, 989-996 (2019)
[14] Read, R. C., The number of \(k\)-colored graphs on labelled nodes, Canad. J. Math., 12, 410-414 (1960) · Zbl 0094.36202
[15] Robinson, R. W., Enumeration of acyclic digraphs, (Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C. 1970) (1970), Univ. North Carolina, Chapel Hill: Univ. North Carolina, Chapel Hill N.C.), 391-399 · Zbl 0219.05065
[16] Robinson, R. W., Counting labeled acyclic digraphs, (New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf. Univ. Michigan, Ann Arbor, Mich. 1971) (1973), Academic Press: Academic Press New York), 239-273
[17] Robinson, R. W., Counting digraphs with restrictions on the strong components, (Combinatorics and Graph Theory ’95, Vol. 1 (Hefei) (1995), World Sci. Publ.: World Sci. Publ. River Edge, NJ), 343-354
[18] Shareshian, J.; Wachs, M. L., Chromatic quasisymmetric functions, Adv. Math., 295, 497-551 (2016) · Zbl 1334.05177
[19] Stanley, R. P., Acyclic orientations of graphs, Discrete Math., 5, 171-178 (1973) · Zbl 0258.05113
[20] Stanley, R. P., (Enumerative Combinatorics, Vol. 2. Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0928.05001
[21] Stanley, R. P., (Enumerative Combinatorics, Vol. 1. Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49 (2012), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1247.05003
[22] Wright, E. M., The number of strong digraphs, Bull. Lond. Math. Soc., 3, 348-350 (1971) · Zbl 0224.05109
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.