graph theory
I saw this question: How to calculate the number of possible connected simple graphs with $n$ labelled vertices
But how can we count graphs with only one dominant vertex (only one vertex in graph that connected to each other node)?
Suppose that we had a set of vertices labelled 1,2,…,n.
In what efficient way do we be able to calculate the number of possible ways the graph can be made?
There are $\binom{n}2=\frac12n(n-1)$ pairs of distinct points. If you do not allow loops or multiple edges, each of these pairs determines one possible edge, and you can have any subset of those possible edges. A set with $\binom{n}2$ members has $2^{\binom{n}2}$ subsets, so there are $2^{\binom{n}2}$ possible graphs without loops or multiple edges.
If you demand that the graphs be connected, the problem becomes very much harder. From your final comment I take it that you are in effect counting labelled graphs. This sequence of numbers is A001187 in the On-Line Encyclopedia of Integer Sequences. If $d_n$ is the number of labelled, connected, simple graphs on $n$ vertices, the numbers $d_n$ satisfy the recurrence
$$\sum_k\binom{n}kkd_k2^{\binom{n-k}2}=n2^\binom{n}2\;,$$
from which it’s possible to calculate $d_n$ for small values of $n$. This recurrence is derived as formula (3.10.2) in Herbert S. Wilf, generatingfunctionology, 2nd edition, which is available for free download here.
According to MathWorld, Brendan McKay’s software package nauty includes a routine that efficiently enumerates such graphs; it’s available here.
If you count unlabelled graphs instead, so that you don’t count isomorphic graphs separately, you get the sequence mentioned by Arturo in the comments.
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
The answer is $n$ multiplied by the number of graphs on $n-1$ vertices with no dominant vertices.
How many graphs on $n$ vertices have no dominant vertices? this can be obtained via inclusion-exclusion, it yields $\sum\limits_{i=0}^n(-1)^i\binom{n}{i}2^{\binom{n-i}{2}}$
Hence the answer to your question is $n\sum\limits_{i=0}^{n-1}(-1)^i\binom{n-1}{i}2^{\binom{n-1-i}{2}}$