0
$\begingroup$

Consider directed graphs on n labelled vertices {1,2,...n}, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many such graphs have exactly two cycles?

$\endgroup$

closed as off-topic by user21820, Saad, RRL, Alexander Gruber Mar 24 at 2:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Saad, RRL, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What are your thoughts on the problem? What approaches have you tried? $\endgroup$ – Santana Afton Mar 23 at 13:04
0
$\begingroup$

Let us use $(m,n)$ to denote the length of the two cycles found in the graph. So consider a graph with $n$ vertices.

For $n=2$ we have $(1,1)$ as a possible cycles length.

For $n=3$, we have $(1,1) (1,2)$

For $n=4$, we have $(1,1) (1,2) (1,3) (2,2)$

For $n=5$, we have $(1,1) (1,2) (1,3) (1,4) (2,2) (2,3)$

For $n=6$, we have $(1,1) (1,2) (1,3) (1,4) (1,5) (2,2) (2,3) (2,4) (3,3)$

From the above pattern, we can deduce a formula. So the formula seems to be defined as follow: for a graph on $n$ vertices, it has $(n-1)+(n-3)+(n-5)+...$ ways to have only $2$ cycles. And in the above sum, a term that gives a negative value should be omitted. Let $f_m(n)$ be the characteristic function that is 0 everywhere except for $n\geq m$. then the solution is $(n-1)f_2(n)+(n-3)f_4(n)+(n-5)f_6(n)+...$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.