Back
 OJDM  Vol.6 No.2 , April 2016
On the Number of Cycles in a Graph
Abstract: In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex vi in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.
Cite this paper: Movarraei, N. and Boxwala, S. (2016) On the Number of Cycles in a Graph. Open Journal of Discrete Mathematics, 6, 41-69. doi: 10.4236/ojdm.2016.62005.
References

[1]   Harary, F. and Manvel, B. (1971) On the Number of Cycles in a Graph. Mat. Casopis Sloven. Akad. Vied, 21, 55-63.

[2]   Chang, Y.C. and Fu, H.L. (2003) The Number of 6-Cycles in a Graph. Bulletin of the ICA, 39, 27-30.

[3]   Alon, N., Yuster, R. and Zwick, U. (1997) Finding and Counting Given Length Cycles. Algorithmica, 17, 209-223.
http://dx.doi.org/10.1007/BF02523189

[4]   Bjorklund, A., Husfeldt, T., Kaski, P. and Koivisto, M. (2009) Counting Paths and Packing in Halves. Lecture Notes in Computer Science, 5757, 578-586.
http://dx.doi.org/10.1007/978-3-642-04128-0_52

[5]   Bjorklund, A., Husfeldt, T., Kaski, P. and Koivisto, M. (2008) The Fast Intersection Transform with Applications to Counting Paths, CoRR, abs/0809.2489.

[6]   Chen, J., Lu, S., Sze, S.H. and Zhang, F. (2007) Improved Algorithms for Path, Matching and Packing Problems. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), Philadelphia, 298-307.

[7]   Koutis, I. (2008) Faster Algebraic Algorithm for Path and Packing Problems. CALP, LNCS 5125, 575-586. Springer, Berlin.

[8]   Kroese, D.P. and Roberts, B. (2007) Estimating the Number of s-t Paths in a Graph. Journal of Graph Algorithms and Applications, 11, 195-214.
http://dx.doi.org/10.7155/jgaa.00142

[9]   Williams, R. (2009) Finding a Path of Length k in O*(2K)Time. Information Processing Letters, 109, 315-318.
http://dx.doi.org/10.1016/j.ipl.2008.11.004

[10]   Boxwala, S.A. and Movarraei, N. (2015) On the Number of Paths of Length 5 in a Graph. International Journal of Applied Mathematical Research, 4, 30-51.
http://dx.doi.org/10.14419/ijamr.v4i1.3874

[11]   Movarraei, N. and Shikare, M.M. (2014) On the Number of Paths of Lengths 3 and 4 in a Graph. International Journal of Applied Mathematical Research, 3, 178-189.

[12]   Boxwala, S.A. and Movarraei, N. (2015) On the Number of Paths of Length 6 in a Graph. International Journal of Applied Mathematical Research, 4, 267-280.
http://dx.doi.org/10.14419/ijamr.v4i2.4314

 
 
Top