Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  David Kohler Apr 3 '11 at 21:04

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  JasonMond Apr 4 '11 at 1:23
    
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. –  Yuval Filmus Apr 4 '11 at 2:31
    
Sounds about right. –  David Kohler Apr 4 '11 at 16:08
    
I see. Thanks! –  JasonMond Apr 5 '11 at 3:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.