4
$\begingroup$

Let $G=(V,E)$ be a graph, and $A$ be its adjacency matrix. Define $n = |V|$.

Given $A$ and a natural number $m \le n$, I'm interested in the following problem:

How many simple cycles of length $m$ exist in $G$?

By simple cycle, I mean no repeated vertices along the cycle is allowed (other than the starting and ending vertices, which coincide).

The problem is NP-hard. However, I'm not asking its complexity; I'm merely interested in whether there is a closed-form expression for computing it. (Thus, computing the expression can be NP-hard.)

  • 0
    @draks: That's one possible difference. Small changes in problem definition may have drastic effects on its computational complexity.2012-11-07

2 Answers 2

1

An answer containing a recursive formula for the number of cycles can be found here.

-1

I think the trace of $A^m$ gives the number of cycles of length $m$ of a graph $G$.

  • 0
    I've got some answers to this question [here](http://math.stackexchange.com/q/177722/19341). Have a look if you're interested...2012-08-03