Research ArticleOpen AccessGoogle Scholar indexed
On the Number of Cycles in a Graph
Department of Mathematics, University of Pune, Pune, India
Department of Mathematics, University of Pune, Pune, India
- 1 Department of Mathematics, University of Pune, Pune, India
- 2 Department of Mathematics, University of Pune, Pune, India
Open Journal of Discrete Mathematics·Volume 06 (2016)·Pages 41–69·Published 31 March 2016·DOI10.4236/ojdm.2016.62005
Copy link · social · email
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 v i in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.
KeywordsAdjacency MatrixCycleGraph TheoryPathSubgraphWalk
- Harary, F. and Manvel, B. (1971) On the Number of Cycles in a Graph. Mat. Casopis Sloven. Akad. Vied, 21, 55-63.
- Chang, Y.C. and Fu, H.L. (2003) The Number of 6-Cycles in a Graph. Bulletin of the ICA, 39, 27-30.
- 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
- 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
- Bjorklund, A., Husfeldt, T., Kaski, P. and Koivisto, M. (2008) The Fast Intersection Transform with Applications to Counting Paths, CoRR, abs/0809.2489.
- 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.
- Koutis, I. (2008) Faster Algebraic Algorithm for Path and Packing Problems. CALP, LNCS 5125, 575-586. Springer, Berlin.
- 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
- Williams, R. (2009) Finding a Path of Length k in O * (2 K )Time. Information Processing Letters, 109, 315-318. http://dx.doi.org/10.1016/j.ipl.2008.11.004
- 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
- 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.
- 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