[seqfan] Enumerating DFS on multigraphs

[Li-yao Xia]

Hello SeqFans,

Consider performing a depth-first search on an unlabelled undirected
multigraph with no single-edge loops. When we cross an edge, the vertex
at the other end is necessarily either unvisited or already in the current
stack. Thus a DFS partitions the set of edges into a set forming a
spanning tree which is rooted at the starting point of the DFS, and a set
of "back edges" linking vertices to their ancestors in that tree.

These trees with back edges can be defined inductively (independently of
any underlying multigraph). I do so succintly here in Haskell, which gives
a simple and efficient enumeration method (measuring size as the number of
edges).

http://blog.poisson.chat/posts/2017-03-01-enumerating-dfs.html

The resulting sequence matches this one https://oeis.org/A258173 which
has no mention of multigraphs, though Dyck paths involve very related
ideas.

My first question is of course: are these sequences (on trees here
and on Dyck paths in the OEIS) indeed the same?

Other types of trees also exist with special edges like back edges to
represent cycles; I know of those arising out of various graph search
strategies (here, DFS), as well as representations for abstract syntax
(lambda terms). I'm curious about this stuff, but don't quite know what
I'm looking for here actually, I guess some keywords are enumeration/
inductive/cyclic. If you have any ideas, I'd be glad to hear them.

Cheers,
Li-yao