Graph Theory – Counting Nonisomorphic Directed Simple Graphs with n Vertices

Question

Edit: This is a closely related question to my earlier post here: Is there a formula for finding the number of nonisomorphic simple graphs that have n nodes?

I'm working on my first exposure to graph theory with a text that seems to leave some definitions rather open- ended, and solutions to similar problems I've seen online might be contradictory. More specific questions to my subject line question are, in a directed graph, what makes it non isomorphic? Is a set of vertices all isolated included? (some solutions say yes, but how can it then be called 'directed?') Can there be multiple graphs in the answer that have the same number of edges and the same in/ out degree totals, or does a distinct signature of edge # and in/ out degree total constitute a distinct graph?

Edit: The text I'm working with doesn't show any examples of bidirectional simple graphs, so I guess I must assume they're not included…

Edit: Here is what I have thus far with my current understanding:

Any guidance would be appreciated. Thanks in advance…

Answer 1

...in a directed graph, what makes it non isomorphic?

As an adjective for an individual graph, non-isomorphic doesn't make sense. You can't sensibly talk about a single graph being non-isomorphic. What we can talk about are sets of graphs which are pairwise non-isomorphic (i.e., any two graphs in the set are not isomorphic).

Intuitively speaking, two graphs $G$ and $G'$ are isomorphic if they have essentially the same structure (and non-isomorphic otherwise). Formally, two graphs are isomorphic if there's an edge-preserving bijection from the vertices of $G$ to the vertices of $G'$.

In the following example, the two red digraphs have essentially the same digraph: there is one node with two out-edges. An edge-preserving bijection (i.e., an isomorphism) in this case is $1 \mapsto 2$, $2 \mapsto 1$ and $3 \mapsto 3$.

There is no such bijection between the red and blue digraphs since they do not have the same in/out-degree sequences.

Is a set of vertices all isolated included? (some solutions say yes, but how can it then be called 'directed?')

The $n$-vertex null digraph (i.e. $n$ vertices and no edges) is consistently regarded as a directed graph.

How many nonisomorphic directed simple graphs are there with n vertices, when n is 2,3, or 4?

To answer this question requires some bookkeeping. The $2$-node digraphs are listed below. Note that I'm including the possibility of bidirectional edges (i.e., an edge from $A$ to $B$ and an edge from $B$ to $A$).

The number of digraphs grows quickly, and is given by Sloane's A000273. For $2$-, $3$- and $4$-node digraphs, the numbers are $3$, $16$, and $218$, respectively (allowing bidirectional edges).

If I was pressed to find these numbers, I'd get my computer to find them by:

1. maintaining a list of "found" digraphs, and
2. generating all possible adjacency matrices, and for each one checking if it's isomorphic to a digraph on the list; it if isn't add it to the list, and if it's not discard this digraph.

This would be quite an inefficient generation method, but would be fast enough for $4$-node digraphs.

Can there be multiple graphs in the answer that have the same number of edges and the same in/ out degree totals, or does a distinct signature of edge # and in/ out degree total constitute a distinct graph?

There can be, here's an example:

and one without bidirectional edges:

---

In the table in the question there's a number of omissions (this is why I'd do it on a computer).

You've correctly observe e.g. that:

are not isomorphic, since the in/out-degrees don't match. For the same reason e.g.:

are also non-isomorphic. Similar omissions (where we flip edge directions) happen in other cases.

I also don't see a oriented 3-cycles with an isolated vertex.

Note: Sloane's A001174 asserts there are 42 digraphs on 4 vertices.