On the number of paths of length 6 in a graph


  • Nazanin Movarraei ph.D student of University of Pune, India.
  • Samina Boxwala HOD, Department of mathematics, Wadia colledge, Pune, India






Adjacency Matrix, Cycle, Graph Theory, Path, Subgraph, Walk.


In this paper, we obtain an explicit formula for the total number of paths of length 6 in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.


[1] Nazanin Movarraei and M. M. Shikare, On the number of paths of lengths 3 and 4 in a graph, International Journal of Applied Mathematical Research, 3(2) (2014), 178-189.

[2] Nazanin Movarraei and S. A. Boxwala, On the number of paths of length 5 in a graph, International Journal of Applied Mathematical Research, 4(1) (2015), 30-51.

[3] F. Harary and B. Manvel, On the number of cycles in a graph, Mat. Casopis Sloven. Akad. Vied 21 (1971),55-63.

[4] N. Alon, R. Yuster and U. Zwick, Finding and counting given length cycles, Algorithmica, 17(1997), 209-223.

[5] I.Tomescu, On the number of paths and cycles for almost all graphs and digraphs, Combinatorica, 6(1) (1986), 73-79.

[6] Eric T. Bax, Algorithms to count paths and cycles, Inf. Process. Lett, 52 (1994), 249-252.

[7] Noga Alon, Raphy Yuster and Uri Zwick, Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, ACM Newyork, 1994, 326-335.

[8] Eric Bax and Joel Franklin, A finite-dierence sieve to count paths and cycles by length, Inf. Process. Lett, 60(4) (1996), 171-176.

[9] Ben Roberts and Drik P. Kroese, Estimating the number of s-t paths in a graph, J. Graph Algorithms and Applications, 11(1) (2007), 195-214.

[10] Ryan Williams, Finding a path of length k in O(2K) time, Inf. Process. Lett, 109(6) (2009), 315-318.

[11] Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto, Counting paths and packing in halves, Lecture Notes in Computer Science, 5757 (2009), 578-586.

[12] Eric. T. Bax, Inclusion and exclusion algorithm for the Hamiltonian path problem, Inform. Process. Lett. 27(4) (1993), 203-207.

[13] A. Bjorklund, T. Husfeldt, P. Kaski, M. Koivisto, The fast intersection transform with applications to counting paths, CoRR, abs/0809.2489 (2008).

[14] J. Chen, S. Lu, S. H. Sze, F. Zhang, Improved algorithms for path, matching and packing problems, 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), Philadelphia, PA, USA, PP. 298-307. Society for Industrial and Applied Mathematics (2007).

[15] Y. Gurevich, S. Shelah, Expected computation time for Hamiltonian path problem, SIAM J. Comput, 16(1987), 486-502.

[16] I. Koutis, Faster algebraic algorithm for path and packing problems, CALP (2008), LNCS 5125, 575-586, Springer.

[17] D. J. A. Welsh, Complexity: Knots, Colouring and Counting, Cambridge University Press, 1993.

[18] Eric. T. Bax, Improvements and bounding for the inclusion and exclusion Hamiltonian algorithm, Caltech-CS-TR-94-11.

[19] B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics, volume 25, (1985), 239-254.

[20] D. Richards, Finding short cycles in a planar graph using separators, Journal of Algorithms, volume 7, (1974), 382-394.

[21] J.A. Bondy and M. Simonovit, Cycles of even length in graphs, Journal of Combinatorial Theory Series B, volume 16, (1974), 97-105.

[22] Lowell W. Beineke and Robin J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, 2007.

[23] F. Harary, Graph Theory, Addison-Wesley, Reading, Mass, 1969.

[24] G. Baroti, On the number of certain hamilton circuits of a complete graph, Periodica Math. Hung, 3 (1973), 135-139.

View Full Article:

Additional Files