...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:
- maintaining a list of "found" digraphs, and
- 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.
First of all, let me state my preconditions. Since you write that there are three graphs with two edges on three vertices it seems you are talking about the labelled case, which is what I will work with from now on. As this is truly a vast field of investigation I will just show you how to calculate these numbers (connected graphs on $n$ nodes having $k$ edges). This should enable you to consult the relevant entries of the OEIS and decide what course to take in your research.
Method I. Let $\mathcal{Q}$ be the combinatorial class of connected graphs and $\mathcal{G}$ the combinatorial class of labelled graphs, all of them. The relation between these two classes is the set-of relation: a graph is a set of connected components. This gives the relation between the two classes:
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{G} = \textsc{SET}(\mathcal{Q}).$$
Translating to generating functions this means that
$$G(z) = \exp Q(z)$$
and hence
$$Q(z) = \log G(z).$$
Now observe that the mixed exponential generating function of $\mathcal{G}$ by vertices and edge count is not difficult to calculate, it is simply
$$G(z) = \sum_{m\ge 0} (1+u)^{m(m-1)/2} \frac{z^m}{m!}
= 1 + \sum_{m\ge 1} (1+u)^{m(m-1)/2} \frac{z^m}{m!}.$$
This yields for $Q(z)$ that
$$Q(z) = \log\left(1+ \sum_{m\ge 1} (1+u)^{m(m-1)/2} \frac{z^m}{m!}\right)
= \sum_{q\ge 1} (-1)^{q+1} \frac{1}{q}
\left(\sum_{m\ge 1} (1+u)^{m(m-1)/2} \frac{z^m}{m!}\right)^q.$$
We are interested in the count for $n$ vertices and $k$ edges where $k\ge n-1$. Note that the term in the parenthesis has minimum degree $q$ in $z$, so we can omit the rest of the series where $q>n.$ This finally yields the formula for the number $q_{n,k}$ of connected labelled graphs with $k$ edges:
$$q_{n,k} = n! [z^n] [u^k] \sum_{q=1}^n (-1)^{q+1} \frac{1}{q}
\left(\sum_{m=1}^n (1+u)^{m(m-1)/2} \frac{z^m}{m!}\right)^q.$$
Substituting concrete values into this formula and entering it into your favorite CAS yields for $k=n-1$ the sequence
$$1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000,\ldots$$
which is OEIS A000272, the tree sequence with value $n^{n-2}.$
Setting $k=n$, we get
$$0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840,\ldots$$
which is OEIS A057500.
Continuing with $k=n+1$ we have
$$0, 0, 0, 6, 205, 5700, 156555, 4483360, 136368414, 4432075200, 154060613850,\ldots$$
which is OEIS A061540.
We could keep going like this but the pattern should be clear.
Method II. A different approach uses the exponential generating function of the set of rooted labelled trees given by
$$T(z) = \sum_{m\ge 1} m^{m-1} \frac{z^m}{m!}.$$
The method is to use a combinatorial decomposition of the relevant classes of graphs in terms of a reduced structure consisting of cycles to which trees are attached at the nodes.
Roughly speaking this structure is what you obtain by removing vertices of degree one from the graph until there are none left, and merging adjacent vertices of degree two. The result is a multigraph. The connected graphs that fall into the class of graphs corresponding to this multigraph are obtained by placing sequences of trees on the multigraph edges such that no self-loops or multi-edges remain.
Note the the so-called excess of a connected graph is the number of edges plus one minus the number of vertices. That means that a tree has excess zero. We will now compute the generating functions for graphs of excess zero, one, and two.
For starters, we have
$$q_{n, n-1} = \frac{1}{n} \times n! [z^n] T(z)$$
which produces the correct sequence (the division accounts for the difference between rooted and unrooted trees).
Next we have that the graphs with excess one counted by $q_{n,n}$ consist of a cycle with trees attached. Summing over the size $m$ of the cycle this yields
$$q_{n, n} = n! [z^n] \sum_{m=3}^n \frac{T(z)^m}{2m}$$
where the two in the denominator accounts for the fact that the cycle is not directed (dihedral group with $2m$ permutations).
Finally in calculating $q_{n,n+1}$ it becomes evident that the underlying structure consists of two cycles joined at a common node or by a path, or a cycle with a chord, which in fact turns out to be two vertices joined by three edges.
Start the inventory. If we have two cycles that are joined at a common node the resulting operator has four or eight automorphisms depending on whether the two cycles have the same size, for a contribution of
$$T(z) \left(\sum_{m_1\ge 2} \sum_{m_2\ge m_1+1} \frac{T(z)^{m_1+m_2}}{4}
+ \sum_{m\ge 2} \frac{T(z)^{2m}}{8}\right).$$
If they are joined by a path we must place a sequence of trees on that path and the contribution is
$$
\frac{T(z)^2}{1-T(z)}\left(
\sum_{m_1\ge 2} \sum_{m_2\ge m_1+1} \frac{T(z)^{m_1+m_2}}{4}
+ \sum_{m\ge 2} \frac{T(z)^{2m}}{8}\right).$$
With the chord there are two cases -- one chord stays empty or all three chords are occupied. For the first case we get
$$T(z)^2 \left(
\sum_{m_1\ge 1} \sum_{m_2\ge m_1+1} \frac{T(z)^{m_1+m_2}}{2}
+ \sum_{m\ge 1} \frac{T(z)^{2m}}{4}\right).$$
The second case produces
$$T(z)^2 \left(
\sum_{m_1\ge 1}\sum_{m_2\ge m_1+1}\sum_{m_3\ge m_2+1}
\frac{T(z)^{m_1+m_2+m_3}}{2}
+ \sum_{m_1\ge 1}\sum_{m_2\ge m_1+1} \frac{T(z)^{m_1+2m_2}}{4}\\
+ \sum_{m_1\ge 1}\sum_{m_2\ge m_1+1} \frac{T(z)^{2m_1+m_2}}{4}
+ \sum_{m\ge 1} \frac{T(z)^{3m}}{12}
\right).$$
Adding these four contributions yields the generating function
$$\frac{T(z)^4}{24} \frac{6-T(z)}{(1-T(z))^3}$$
and the formula
$$q_{n, n+1} = n! [z^n] \frac{T(z)^4}{24} \frac{6-T(z)}{(1-T(z))^3}.$$
As for the practical utility of this formula it can be treated by Lagrange inversion
to give a closed form suitable for computation.
The species of labelled trees has the specification
$$\mathcal{T} =
\mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$
Extracting coefficients via Lagrange inversion we have
$$q_{n,n+1}
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\frac{T(z)^4}{24} \frac{6-T(z)}{(1-T(z))^3} dz.$$
Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and
$dz = (\exp(-w) - w\exp(-w)) \; dw$
to get
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(w(n+1))}{w^{n+1}}
\times \frac{w^4}{24} \frac{6-w}{(1-w)^3}
\times (\exp(-w) - w\exp(-w)) dw
\\ = \frac{1}{24} n! \frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(wn)}{w^{n-3}} \frac{6-w}{(1-w)^2} dw
\\ = \frac{1}{24} n! \frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{\exp(wn)}{w^{n-3}}
\left(\frac{1}{1-w} + 5\frac{1}{(1-w)^2}\right) dw.$$
Extracting coefficients we obtain
$$q_{n,n+1} = \frac{1}{24} n!
\sum_{q=0}^{n-4}
\frac{n^q}{q!} (1 + 5 (n-4-q+1))
\\ = \frac{1}{24} n!
\sum_{q=0}^{n-4}
\frac{n^q}{q!} (5 (n-q) - 14).$$
Concluding observation. We have made repeated use of the labelled enumeration formula
$$B(z) = \frac{A(z)^n}{|G|}$$ which produces the exponential generating function $B(z)$ of objects enumerated by $A(z)$ being distributed into $n$ slots acted on by a permutation group $G,$ where the size of the compound object is the sum of the constituent sizes. This is the lablled counterpart of the Polya Enumeration Theorem.
Addendum. What follows is the Maple code for the above closed formula in terms of the mixed generating function, which is intended for sequence identification and not necessarily for computation, there are recurrences for that, consult e.g. Graphical Enumeration by Harary and Palmer.
with(combinat);
gf :=
proc(n)
option remember;
local subgf;
subgf := add((1+u)^(m*(m-1)/2)*z^m/m!, m=1..n);
expand(n!*coeftayl(add((-1)^(q+1)/q*subgf^q, q=1..n),
z=0, n));
end;
qval :=
proc(n, k)
option remember;
coeff(gf(n), u, k);
end;
Addendum. Thu Nov 27 01:12:06 CET 2014. It was pointed out to me
in a personal communication that the above closed formula performs
extremely poorly where memory and time complexity are concerned. We
can however create a very fast equivalent by performing the
coefficient extraction for $[z^n]$ before the main computation.
Let us recall the formula:
$$q_{n,k} = n! [z^n] [u^k] \sum_{q=1}^n (-1)^{q+1} \frac{1}{q}
\left(\sum_{m=1}^n (1+u)^{m(m-1)/2} \frac{z^m}{m!}\right)^q.$$
The key here is to recognize that we are iterating over integer
partitions $\lambda\vdash n$ of length $l(\lambda) = q.$ The
coefficient on $z^n$ is given by
$$\frac{1}{n!} {n\choose \lambda}.$$
The exponent of $(1+u)$ is given by
$$\sum_{\lambda_i\in\lambda} \lambda_i(\lambda_i-1)/2.$$
Finally the multiplicity of each partition i.e. the number of
corresponding compositions when $\lambda = 1^{f_1} 2^{f_2} 3^{f_3}
\cdots$ is $${q\choose f}.$$
This gives the generating function for $n$ fixed which is
$$\large{g_n(u) =
\sum_{\lambda\vdash n}
\frac{(-1)^{q+1}}{q} {n\choose\lambda} {q\choose f}
(1+u)^{\sum_{\lambda_i\in\lambda} \lambda_i (\lambda_i-1)/2}}$$
where $q=l(\lambda)$ and $f$ represents the multiplicities in the
partition so that $\lambda = 1^{f_1} 2^{f_2} 3^{f_3}\cdots$
This formula would appear to be practical even for large values.
Here is the sequence of the enumeration of connected labeled graphs
OEIS A001187 up to $n=30,$
computed by Maple almost instantly.
These values are obtained by setting $u=1$ in the above formula,
which avoids the cost of computing with those polynomials in $u,$
giving
$$\large{q_n =
\sum_{\lambda\vdash n}
\frac{(-1)^{q+1}}{q} {n\choose\lambda} {q\choose f}
2^{\sum_{\lambda_i\in\lambda} \lambda_i (\lambda_i-1)/2}}$$
1,
1,
4,
38,
728,
26704,
1866256,
251548592,
66296291072,
34496488594816,
35641657548953344,
73354596206766622208,
301272202649664088951808,
2471648811030443735290891264,
40527680937730480234609755344896,
1328578958335783201008338986845427712,
87089689052447182841791388989051400978432,
11416413520434522308788674285713247919244640256,
2992938411601818037370034280152893935458466172698624,
1569215570739406346256547210377768575765884983264804405248,
1645471602537064877722485517800176164374001516327306287561310208,
34508369722950116062601714914260936851437546115328069963470233458442...
24,
14473931784581530777452916362195345689326195578125463551466449404195...
748970496,
12141645838784034832247737828641414668703840762841807733278352921867...
1227143860518912,
20370329409143419676922561585800800631483979568699568444273558936889...
94716051486372603625472,
68351532186533737864736355381396298734910952426503780423683990730318...
777915378756861378792989392896,
45869953864873439868450361909803259294922972126320661426113608442339...
62960637520118252235915249481987129344,
61565621838274124223450863197683805128241193119763036274703372417422...
2395343543109861028695816566950855890811486208,
16526397434352809199623091939881315484783346104710447766695225793956...
4080953537482898938408257044203946031706125367800496128,
88725425253946309579607515290733826999038832348034303708272765654674...
479763074364231597119435621862686597717341418971119460584259584,
Maple took $181.311$ seconds (three minutes) to compute the generating
function for $n=38$ and $1346$ MB of used memory using the initial
unsimplified version of the formula and $4.392$ seconds and $90$ MB
using the fast version, a stunning improvement. Only the recurrences
by Harary and Palmer and by E.M. Wright will do better.
This was the Maple code.
with(combinat, partition);
gf2 :=
proc(n)
local s, q, p, mcf1, mcf2, li;
s := 0;
for p in partition(n) do
q := nops(p);
mcf1 := n!/mul(li!, li in p);
mcf2 :=
q!/mul(li!, li in
map(ent -> ent[2], convert(p, multiset)));
s := s + (-1)^(q+1)/q *
mcf1*mcf2* (1+u)^add(li*(li-1)/2, li in p);
od;
expand(s);
end;
Concluding remark. At this point there is nothing to stop us from
extracting the coefficient of $[u^k]$ as well, giving the formula
$$\large{q_{n,k} =
\sum_{\lambda\vdash n}
\frac{(-1)^{q+1}}{q} {n\choose\lambda} {q\choose f}
{\sum_{\lambda_i\in\lambda} \lambda_i (\lambda_i-1)/2 \choose k}}$$
Another optimization. The memory usage of the above is not quite optimal and can be improved by allocating partitions one at a time instead of all at once.
This gives the following.
gf2 :=
proc(n)
local s, q, p, mcf1, mcf2, li;
option remember;
s := 0;
p := firstpart(n);
while type(p, list) do
q := nops(p);
mcf1 := n!/mul(li!, li in p);
mcf2 :=
q!/mul(li!, li in
map(ent -> ent[2], convert(p, multiset)));
s := s + (-1)^(q+1)/q *
mcf1*mcf2* (1+u)^add(li*(li-1)/2, li in p);
p := nextpart(p);
od;
expand(s);
end;
With this version we are only limited by time and not space. Here is the total count for $n=50:$
57775629806264131981532128463353986108213291999872288565750767218860631769...
6301924134068233518707877841769252356274834883678320922291785288952259...
3249600859338855724814764410440416662456329476306676699006233890696555...
2334495222211417966008667425130052344927925607827177068266427605834927...
5922600493471476178420154378012048571333436567365397136152469165480980...
158369042006016
Addendum Thu Dec 4 00:48:39 CET 2014. For the purpose of
collecting everything in one place let me just briefly comment on
those recurrences, following Harary and Palmer.
They use an extremely simple observation namely that if we have two
formal power series related by a log-relationship as in
$$\sum_{q\ge 0} a_q z^q
= \log\left(\sum_{q\ge 0} A_q z^q \right)$$
then differentiation (which is a standard trick and is often used on
recurrences involving the tree function) gives
$$\sum_{q\ge 1} q a_q z^{q-1}
= \frac{\sum_{q\ge 1} q A_q z^{q-1}}{\sum_{q\ge 0} A_q z^q}.$$
Re-write this so that the Cauchy product appears more clearly:
$$\left(\sum_{q\ge 1} q a_q z^{q-1}\right)\times
\left(\sum_{q\ge 0} A_q z^q\right) =
\sum_{q\ge 1} q A_q z^{q-1}.$$
Comparing coefficients we obtain for the coefficient on $z^q$
$$\sum_{m=0}^q A_{q-m} (m+1) a_{m+1} = (q+1) A_{q+1}$$
This yields
$$(q+1) a_{q+1} =
(q+1) A_{q+1} - \sum_{m=0}^{q-1} A_{q-m} (m+1) a_{m+1}$$
or finally for $q\ge 1$
$$a_{q+1} =
A_{q+1} - \frac{1}{q+1} \sum_{m=0}^{q-1} A_{q-m} (m+1) a_{m+1}.$$
Note that we are working with exponential generating functions so we
are using the values $b_q = q! \times a_q$ and $B_q = q! \times A_q.$
Multiply the recurrence by $(q+1)!$ to get
$$b_{q+1} =
B_{q+1}
- \sum_{m=0}^{q-1} q! \frac{B_{q-m}}{(q-m)!}
\frac{b_{m+1}}{m!}.$$
which finally yields
$$b_{q+1} =
B_{q+1} - \sum_{m=0}^{q-1} {q\choose m} B_{q-m} b_{m+1}.$$
In the present case we have $B_q = (1+u)^{q(q-1)/2}.$
It is important for these recurrences to work that we put
$B_0=B_1=b_0=b_1 = 1.$
This recurrence is amazingly fast. With memoization turned on Maple
took $58$ seconds to compute $g_{50}(u)$ using the partition iteration
method and $1.25$ seconds using the recurrence. For $g_{55}(u)$ the
timings were $145$ seconds vs. $1$ second. It does not get any faster
than this.
gf3 :=
proc(n)
option remember;
local s, B, q;
if n < 2 then return 1 fi;
B :=
proc(m)
if m < 2 then return 1 fi;
(1+u)^(m*(m-1)/2);
end;
q := n-1;
s := B(q+1)
- add(binomial(q,m)*B(q-m)*gf3(m+1),
m=0..q-1);
expand(s);
end;
Definitely the last addendum. We can perform coefficient
extraction on the terms of this last formula to get
$$q_{n, k} =
\begin{cases}
0 \quad\text{if}\quad k\lt n-1 \quad\text{or}\quad k\gt n(n-1)/2 \\
n^{n-2} \quad\text{if}\quad k = n-1,
\quad\text{and otherwise}\\
{n(n-1)/2\choose k}
- \sum_{m=0}^{n-2} {n-1\choose m}
\sum_{p=0}^k {(n-1-m)(n-2-m)/2 \choose p} q_{m+1, k-p}.
\end{cases}$$
The complexity of this formula is quite poor as it makes $O(nk)$
recursive calls with $k$ being on average quadratic in $n$. The reader
is invited to do the combinatorics and produce a better recurrence.
As it stands the fastest version is the one that uses the recurrence
derived from the log-relationship, the procedure gf3.
q :=
proc(n, k)
option remember;
local res;
if k < n-1 or k > n*(n-1)/2 then return 0 fi;
if k = n-1 then return n^(n-2) fi;
res := binomial(n*(n-1)/2, k)
- add(binomial(n-1, m)*
add(binomial((n-1-m)*(n-2-m)/2, p)*q(m+1, k-p),
p=0..k), m=0..n-2);
res;
end;
gf4 :=
proc(n)
option remember;
add(q(n,k)*u^k, k=n-1..n*(n-1)/2);
end;
As it turns out some optimizations that I thought Maple would do
automatically must be implemented manually, giving the following
optimized code. This is better than gf4 but still a far cry from
what gf3 produces. For that it would appear to need a fundamental
change in the mechanism of the recurrence.
qq :=
proc(n, k)
option remember;
local res, res1, m, p;
if k < n-1 or k > n*(n-1)/2 then return 0 fi;
if k = n-1 then return n^(n-2) fi;
res := binomial(n*(n-1)/2, k);
for m from 0 to n-2 do
res1 := 0;
for p from max(0, k-1/2*(m+1)*m) to k-m do
res1 := res1 +
binomial((n-1-m)*(n-2-m)/2, p)*qq(m+1, k-p)
od;
res := res - binomial(n-1, m)*res1;
od;
res;
end;
gf5 :=
proc(n)
option remember;
add(qq(n,k)*u^k, k=n-1..n*(n-1)/2);
end;
The interested reader may also want to consult this
MSE link.
Best Answer
EDIT: The software at OEIS A138107 is sufficient to answer this post.