1
$\begingroup$

Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known as connected digraphs with uniform outdegree 1, or connected functions, or connected mapping patterns, or rings and branches with $n$ edges). The number of such digraphs is sequence A002861 on the Online Encyclopedia of Integer Sequences.

We have discovered an enumeration algorithm with the following properties:

  • every connected functional digraph (up to isomorphism) is generated;
  • no duplicates (with respect to graph isomorphism) are generated;
  • each functional digraph is generated in polynomial time (with respect to $n$);
  • the algorithm uses polynomial auxiliary space, not counting the output (which is, of course, write-only).

Until now, we were not able to find an algorithm with these four properties in the literature (actually, we haven’t found any nontrivial algorithm at all). Is there any known result about this problem or the related problem of enumerating all, not necessarily connected functional digraphs (A001372)?

Improve this question
$\endgroup$
6
  • $\begingroup$ By the way, I’m wondering if this question would actually be better asked on MathOverflow. Any opinions on that? $\endgroup$
    – Antonio E. Porreca
    yesterday
  • 1
    $\begingroup$ Just following your OEIS link, in the 'formula' field, it gives an equivalence (to the CIK transform of directed trees). I haven't encountered the 'CIK' transform before, and the first description of it I can find is oeis.org/A032199 , but it does sound like a constructive enumeration of the objects in the sequence (if some details are filled in) and not just the construction of the number of objects. Can you comment on whether this meets the criteria of an algorithm you ask about? $\endgroup$
    – JimN
    yesterday
  • $\begingroup$ @JimN I am… really not sure. The description on A032199, although it does indeed seem like it can generate the actual objects, appears to be a calculation “by hand”, and the general description of the CIK transform seems to define it in terms of the CHK transform, based on the AIK transform, and the latter coincides with the INVERT transform, which works on the generating function of the sequence rather than on the $n$-th term. Knowing almost nothing about generating functions right now, I unfortunately don’t know how to comment. $\endgroup$
    – Antonio E. Porreca
    yesterday
  • $\begingroup$ Okay, let's instead try a constructive version of the 'Comment' field of A002861. Does your discovered enumeration algorithm go like this: generate all the functions that are on a tree-shape, then generate all the functions that are a 2-cycle with path-like branches coming out of the cycle, then generate all the functions that contain a 3-cycle with branches, and so on up until you get to one n-cycle? $\endgroup$
    – JimN
    21 hours ago
  • 1
    $\begingroup$ I see - thanks for the description. I don't see anything on the OEIS page that suggests that construction, and (getting back to your original question) I'm not aware of any explicitly-described algorithm to generate these... Another thought: I believe Nauty's geng has a directed graph version or option, and probably takes some parameters for generating (di)graphs with maximum/minimum (in/out)degrees... of course, this does a kind of brute-force generation and filters out isomorphic duplicates, but it does generate things and maybe it would be worthwhile to time-test yours against that $\endgroup$
    – JimN
    17 hours ago

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.