Given a directed graph $C$ that only contains a directed cycle of length $L$ (and all resulting sub-cycles), that visits each node at least once,

$$C=(V, D)$$

where $V$ is a fixed set of vertices and $D$ is a set of directed edges, and:

$$|V| = N$$

$$|D| = L$$

$$ 1 \leq \deg^+(v) \leq 2, v \in V$$

How many directed graphs $G=(V,E)$, where $E$ is a set of directed edges and,

$$ \deg^+(v) = 2, v \in V$$

contain $C$? I am not considering $G$ that contains a graph isomorphic to $C$, I am only interested in $G$ that contain exactly $C$.

That is, if F is the set of all G that contain exactly C as a subgraph, and

$$ n = |F| $$

what is n?

  • $\begingroup$ This is not precise enough, there are clearly infinitely many graphs containing this one... what are your restrictions? Do you want to count the number of such graphs with a fixed number of vertices? Or edges? What forbids you from simply asking yourself how starting from that graph $C$ you would build a larger graph and count them like that? $\endgroup$ – David Kohler Apr 3 '11 at 21:04

Let $a_0,a_1,a_2$ be the vertices with out-degree $0,1,2$ in $C$; so $a_0+a_1+a_2=N$. Following David's advice, it seems that since you're (for now) ignoring the in-degree, the number of graphs is exactly $$ \binom{N+1}{2}^{a_0} N^{a_1}. $$ Now according to your (current) spec, in fact $a_0 = 0$, and moreover $a_1 + 2a_2 = L$. Since $a_2 = N-a_1$, we get that $a_1 + 2(N-a_1) = L$ and so $a_1 = 2N-L$. Therefore $$ n = N^{2N-L}. $$

  • $\begingroup$ Could you explain how you derived $\binom{N+1}{2}^{a_0} N^{a_1}$ as the number of graphs? Would you prefer I set this up as another question? $\endgroup$ – JasonMond Apr 4 '11 at 1:23
  • $\begingroup$ This is just the possible number of arrows that can be added from a given vertex. If we need to add one more arrow then we have $N$ possibilities - that's easy. If we need to add two then you might think we have $N^2$, but in fact out of these, $N(N-1)$ appear twice. $\endgroup$ – Yuval Filmus Apr 4 '11 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy