On the number of paths of length 6 in a graph

  • Authors

    • Nazanin Movarraei ph.D student of University of Pune, India.
    • Samina Boxwala HOD, Department of mathematics, Wadia colledge, Pune, India
    2015-03-10
    https://doi.org/10.14419/ijamr.v4i2.4314
  • Adjacency Matrix, Cycle, Graph Theory, Path, Subgraph, Walk.

  • Abstract

    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.

  • References

    1. [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.

  • Downloads

    Additional Files

  • How to Cite

    Movarraei, N., & Boxwala, S. (2015). On the number of paths of length 6 in a graph. International Journal of Applied Mathematical Research, 4(2), 267-280. https://doi.org/10.14419/ijamr.v4i2.4314

    Received date: 2015-02-07

    Accepted date: 2015-03-02

    Published date: 2015-03-10