3
$\begingroup$

Consider the set $S$ of multigraphs defined recursively as follows:

Example Graph Class

A graph $G$ is in $S$ if(f)

  1. $G$ is a loop on a single vertex, or
  2. $G$ may be obtained by selecting a graph $G'\in S$ and applying one of the following operations:

    • Add an edge between two extant vertices, or
    • Split an edge (add a vertex halfway along an edge) and add an edge between the newly created vertex and any vertex.

I am studying a number of recursively constructed graph classes similar to this example. In particular, for each of these classes I would like to count the number of unlabeled graphs that can be produced after $n$ applications of a set of graph operations similar to the above.

Continuing our example, the graphs counted for $n=1,2,$ and $3$ are pictured here:

Graphs

My questions:

  1. Are there are any general combinatorial techniques used to count graphs in this setting?

  2. Regardless of the existence of general techniques, how might you go about counting my example above?

I am aware of the Polya enumeration theorem, but was unsure if the extra recursive information might be better leveraged with some other technique, or whether this particular statistic would make it difficult to apply Polya's theorem. Importantly, whether or not a graph is counted for a particular $n$ is not directly related to neither the number of vertices nor the number of edges in the graph.

Thank you.

$\endgroup$
  • $\begingroup$ 1,2,5, looks suspiciously like Catalan numbers, and your recursion could perhaps be explained by that... but I am not sure. Can you do the next level as well? Maybe only the planar ones are Catalan... $\endgroup$ – Per Alexandersson Aug 18 '16 at 0:00
  • 1
    $\begingroup$ Thank you for your comments! Max Alekseyev, this is just an example, so I'll call the definition correct and the picture wrong. I have updated the image accordingly. Per Alexandersson, thanks to Max's correction the sequence is now $1,3,9...$ -- certainly not the Catalan numbers $\endgroup$ – JosephSlote Aug 18 '16 at 20:29
  • 1
    $\begingroup$ at least the difference between the number of edges and the number of vertices is the level minus one, which means that you possibly want to label the regions of your graph - except that the graphs won't always be planar :-( $\endgroup$ – Martin Rubey Aug 18 '16 at 20:53
  • 1
    $\begingroup$ Sorry I don't understand your last phrase (starting with "Importantly..."), could you please explain more? What do you mean by a graph being correlated with the number of its vertices or edges? $\endgroup$ – მამუკა ჯიბლაძე Aug 22 '16 at 7:21
  • 2
    $\begingroup$ I see (more or less...). Something similar I've seen is in one of the (very many) approaches to meander enumeration - see e. g. the diagram on page 508 here. Note however that with meanders one gets a tree, i. e. each meander is generated exactly once, and still the approach has not been developed far enough to give anything definite. $\endgroup$ – მამუკა ჯიბლაძე Aug 22 '16 at 20:24
2
$\begingroup$

Your picture is missing some graphs. There should be 11 graphs on level 3. You are for example missing the graph with edges {12,12,23,23,33}. The sequence I get is {1, 3, 11, 61, 484,...} with no hit in the OEIS.

Relevant Mathematica code:

(* Define lex-smallest version of graph structure. *)

GraphCanonicalize[struct_List] := Module[{verts, perms, range},
   verts = Union@Cases[struct, _Integer, 2];
   range = Range@Length@verts;
   perms = 
    Sort@Table[
      Sort[Sort /@ (struct /. Thread[verts -> p])], {p, 
       Permutations[range]}];
   Do[
    GraphCanonicalization[pp] = First[perms];
    , {pp, perms}];
   GraphCanonicalization[struct] = First[perms];
   ];
GraphCanonicalization[struct_List] := (GraphCanonicalize[struct]; 
   GraphCanonicalization[struct]);

graphs[1] := {{{1, 1}}};
graphs[n_Integer] := Module[{childs, prev = graphs[n - 1]},

   childs[g_] := Module[{vs = Union[Join @@ g]},

     GraphCanonicalization /@ Join[

       (* Add edge *)
       Table[
        Append[g , edge]
        , {edge, Subsets[vs, {2}]}]
       ,
       (* Add loop *)
       Table[
        Append[g , {v, v}]
        , {v, vs}]

       ,
       (* Split edge and add extra edge to this new vertex. *)

       Join @@ Table[
         Join[
          DeleteCases[g, edge, 1, 
           1], { {edge[[1]], n}, {edge[[2]], n}, {nv, n}}]
         , {edge, g}, {nv, Append[vs, n]}]
       ]

     ];

   Union[Join @@ (childs /@ prev)]
   ];

Table[Length@graphs[k], {k, 1, 5}]
$\endgroup$
  • $\begingroup$ Hi Per Alexandersson, thank you for your answer and for the time you spent coding an enumeration. I should have been more explicit in my question-asking, but I was wondering if there were any extant theoretical tools that might be of use here, or if this type of problem has been addressed before. I am not directly interested in the sequence that derives from the example I provided, but rather techniques. I will strive to fix my picture once and for all. $\endgroup$ – JosephSlote Aug 22 '16 at 20:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.