Finding all cycles of a certain length in a graph Hello,
I'm looking for a formula or algorithm to find the number of cycles of a certain length $k$ in a graph. 
I know that $(A^k)_{ii}$ gives me the number of cycles from vertex $i$ to itself ($A$ is the adjacency matrix), but these are cycles that might contain the same vertex twice.
I have to tried to devise some sort of a recurrence formula but to no avail.
Thanks!
 A: Is your graph topologically planar or non-planar, weighted or unweighted, directed or undirected?
Do you want an algorithm and/or a formula/bound?
For bounds on planar graphs, see Alt et al. On the number of simple cycles in planar graphs
For an algorithm, see the following paper.  It incrementally builds k-cycles from (k-1)-cycles and (k-1)-paths without going through the rigourous task of computing the cycle space for the entire graph.  It also handles duplicate avoidance. 


*

*Hongbo Liu; Jiaxin Wang; , "A new
way to enumerate cycles in graph,"
Telecommunications, 2006. AICT-ICIW
'06. International Conference on
Internet and Web Applications and
Services/Advanced International
Conference on , vol., no., pp. 57-
57, 19-25 Feb. 2006 doi:
10.1109/AICT-ICIW.2006.22 URL: http://www.ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1602189&isnumber=33674
A: If you consider only simple cycles (every vertex visited at most once) then this problem is NP-complete, so no polynomial (in $|G|$ and $k$) algorithm is known.
If non-polynomial algorithms are ok, you can use dynamic programming algorithm with complexity $O(\sum_{i=0}^{i\le k}\binom{n}{i}n^2)$. This algorithm calculates for every subset $S$ of at most $k$ vertices and every vertex $v \in S$ from this subset the number of paths that goes through all vertices from $S$ and has $v$ as the last vertex.
