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!



Finding all cycles of a certain length in a graph
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](http://www.ams.org/mathscinet-getitem?mr=1731975)


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>


