8
$\begingroup$

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: enter image description here

Any guidance would be appreciated. Thanks in advance...

$\endgroup$
3
  • $\begingroup$ Hi - you should probably state that you've asked a very closely related question at math.stackexchange.com/questions/353053 ... $\endgroup$ – Dan Stowell Apr 7 '13 at 17:56
  • 1
    $\begingroup$ A directed simple graph is a structure consisting of the set of vertices and a binary relation that is irreflexive. For the case of the disconnected graph, the relation is empty, and there is one such structure up to isomorphism for each different number of vertices. The Wikipedia pages on graph theory are a good source if you are struggling with an unclear textbook. $\endgroup$ – András Salamon Apr 7 '13 at 18:53
  • $\begingroup$ @Dan Done, thanks.. $\endgroup$ – StatsViaCsh Apr 7 '13 at 19:22
9
$\begingroup$

...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$.

Examples of isomorphic/non-isomorphic digraphs on 3 nodes

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 non-isomorphic digraphs on 2 nodes

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:

Non-isomorphic digraphs with the same in-degree and out-degree sequences

and one without bidirectional edges:

Non-isomorphic digraphs with the same in-degree and out-degree sequences


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:

Two non-isomorphic digraphs on 3 nodes

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

Three non-isomorphic digraphs on 4 nodes

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.

Omissions from the list

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

$\endgroup$
5
  • $\begingroup$ Thank you VERY much for taking the time and attention to detail. Part of my complaint about my text stems from the fact that no examples (and no definitions) allow bidirectional edges. I'm editing my original post to state as such. $\endgroup$ – StatsViaCsh Apr 7 '13 at 20:20
  • 1
    $\begingroup$ In the case where bidirectional edges are not allowed, the sequence is Sloane's A001174; and the directed $6$-cycle and the union of two disjoint directed $3$-cycles have the same in/out-degree sequence. $\endgroup$ – Douglas S. Stones Apr 7 '13 at 20:27
  • $\begingroup$ NB: You might find it simpler to consider the non-isomorphic undirected graphs; then add orientations to the edges in all possible ways. $\endgroup$ – Douglas S. Stones Apr 8 '13 at 17:12
  • $\begingroup$ Great advice. Answered.. $\endgroup$ – StatsViaCsh Apr 8 '13 at 20:56
  • $\begingroup$ The link oeis.org/A000273 is very useful. $\endgroup$ – youkaichao May 2 at 8:43
1
$\begingroup$

Multiple questions here - it might be better to unpack them.

Nonisomorphic: I guess the point is to count, for example, A->B and A<-B as isomorphic.

Isolated vertices: yes the set of vertices with no arcs is generally included unless explicitly stated. Consider the definition of directed graph, and the definition does not exclude the arcs being an empty set. Similarly the set of vertices could be an empty set (and the arcs too, in that case).

Multiple graphs with same in/outdegree totals: yes it can happen, of course. Inspect "A->B->C" vs "A->B<-C".

$\endgroup$
0
0
$\begingroup$

There is a formula:$$n = \left\lfloor\frac{v^e}{e!·v}\right\rfloor,$$where $v$: number of vertices, $e$: number of edges, $n$: number of nonisomorphic directed simple graphs.

$\endgroup$

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.