Background:
I’m helping a colleague with a theoretical problem in ecology, and I haven’t quite the background to solve this myself. However, I can state the problem clearly, I think:
Problem statement:
We’d like to enumerate and count (somehow) the number of connected, nonisomorphic graphs of $N$ vertices, where edges are categorized into three types, each representing a specific ecological interaction:
- Green represents a bidirectional Mutualism, where any pair of vertices may be connected and the order of vertices does not matter. Thus, $A \leftrightarrow B$ is always equivalent to $B \leftrightarrow A$.
- Blue represents a directional Competition, with edges capable of pointing either way between any pair of vertices. Here, the order of vertices matters, and $A \rightarrow B$ is always equivalent to $B \leftarrow A$, but sometimes $A \rightarrow B$ is equivalent to $A \leftarrow B$ under an isomorphism between two graphs.
- Red represents a directional Predation, with edges capable of pointing either way between any pair of vertices, exactly similar to Blue.
Examples of isomorphisms for $N=3$:
- $A \mathop{\longrightarrow}\limits^{\text{Red}} B \mathop{\longrightarrow}\limits^{\text{Red}} C \enspace\equiv\enspace A \mathop{\longleftarrow}\limits^{\text{Red}} B \mathop{\longleftarrow}\limits^{\text{Red}} C$
- $A \mathop{\longrightarrow}\limits^{\text{Blue}} B \mathop{\longrightarrow}\limits^{\text{Blue}} C \mathop{\longrightarrow}\limits^{\text{Blue}} A \enspace\equiv\enspace A \mathop{\longleftarrow}\limits^{\text{Blue}} B \mathop{\longleftarrow}\limits^{\text{Blue}} C \mathop{\longleftarrow}\limits^{\text{Blue}} A$
- $A \mathop{\longrightarrow}\limits^{\text{Blue}} B \mathop{\longleftarrow}\limits^{\text{Blue}} C \mathop{\longleftarrow}\limits^{\text{Blue}} A \enspace\equiv\enspace A \mathop{\longleftarrow}\limits^{\text{Blue}} B \mathop{\longrightarrow}\limits^{\text{Blue}} C \mathop{\longrightarrow}\limits^{\text{Blue}} A$
- $A \mathop{\longrightarrow}\limits^{\text{Blue}} B \mathop{\longrightarrow}\limits^{\text{Red}} C \mathop{\longleftrightarrow}\limits^{\text{Green}} A \enspace\equiv\enspace A \mathop{\longleftarrow}\limits^{\text{Red}} B \mathop{\longleftarrow}\limits^{\text{Blue}} C \mathop{\longleftrightarrow}\limits^{\text{Green}} A$
Known answers for trivial values of N:
- For $N=1$, there are 0 graphs satisfying the criteria, because there are no interspecies interactions, and the only graph is also unconnected.
- For $N=2$, there are 3 graphs satisfying the criteria, one for each of the colored edges connecting the two vertices. Note that there aren’t 5, because 2 pairs of graphs are isomorphisms. ($A \rightarrow B$ is an isomorphism of $A \leftarrow B$ for each color Red and Blue.)
- For $N=3$, it gets a complicated fast, but it is known that there are 40 graphs satisfying the criteria. This has been verified both by hand enumeration with clear plastic cutouts and by a computer program to examine all candidates and exclude isomorphisms uncovered by simple flips and rotations.
Beyond that, the problem becomes difficult to think about visually in a way that guarantees that all isomorphisms are found and eliminated. Even identifying all possible flips, twists, exchanges, and rotations of the graphs with $N=4$ is a bit of a challenge to get right in a hand-written program. I suspect a more general approach using graph theory, group theory, and/or combinatorics will lead to answers much more readily.
Objectives:
- Primary Goal: We’d like to establish some formula (not necessarily in closed form) for computing the count, and be able to evaluate the formula for values of $N$ up to, say, 10, if possible. This might be accomplished with a computer program written in Mathematica or Haskell.
- Secondary Goal: We’d like to enumerate all connected non-isomorphic graphs with $N$ vertices (under the Green/Blue/Red edge conditions). Ideally, this would be an oriented incidence matrix that we could transform into input for Graphviz.
This mathematical exploration aims to contribute insights into the dynamics of multi-species interactions in ecological systems. Advice from experts in graph theory, combinatorics, and group theory on how to approach this problem would be very helpful. Your guidance on tackling this mathematical challenge, along with strategies for creating a software program to achieve the primary or secondary goal, would provide valuable perspectives on ecological interaction modeling.
Upper bound:
We know trivially that the total count is bounded by $6^{T(N)}$, where $T(N)={N(N-1)\over 2}$, i.e., the $N$th triangular number or the number of edges in a graph of $N$ vertices. The base of 6 here is due to there being six possible edge states: None, Green, Blue forward, Blue backward, Red forward, and Red backward. That part is trivial and easy; the hard part is excluding isomorphic redundancies, of which there are many. For example, for $N=3$, the set of candidates is initially 216, but is quickly whittled down to 40 after removing non-connected graphs and coalescing isomorphisms.
