Symbolic method and directed graph enumeration

2019/03/22 by Élie de Panafieu, de Panafieu, Élie, Sergey Dovgal +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1903.09454

7 pages, 3 figures

arxiv created 2019/06/12 · arxiv updated 2019/06/13

Abstract

We introduce the arrow product, a systematic generating function technique for directed graph enumeration. It provides short proofs for previous results of Gessel on the number of directed acyclic graphs and of Liskovets, Robinson and Wright on the number of strongly connected directed graphs. We also recover Robinson's enumerative results on directed graphs where all strongly connected components belong to a given family.

Related

• Enumeration of graphs with given weighted number of connected components
• Generating Functions of Some Families of Directed Uniform Hypergraphs
• Enumeration of balanced finite group valued functions on directed graphs
• Counting paths in directed graphs
• Enumerating Cliques in Direct Product Graphs