1
$\begingroup$

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?

  • 0
    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?2011-04-03

1 Answers 1

1

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

  • 0
    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.2011-04-04