On the Number of Paths of Lengths 3 and 4 in a Graph

  • Authors

    • Nazanin Movarraei ph.D student of University of Pune, India.
    • Maruti Shikare Faculty, University of Pune, India.
    2014-05-16
    https://doi.org/10.14419/ijamr.v3i2.2409

  • Abstract

    In this paper, we obtain explicit formulae for the total number of paths of lengths 3 and 4 in a simple graph G. We also determine some formulae for the number of paths of lengths 3 and 4 each of which starts from an specific vertex vi and for the number of vi-vj paths of lengths 3 and 4 in a simple graph G, in terms of the adjacency matrix and with the helps of combinatorics.

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

  • References

    1. F. Harary and B. Manvel, On the number of cycles in a graph, Mat. Casopis Sloven. Akad. Vied 21 (1971),55-63.
    2. I.Tomescu, On the number of paths and cycles for almost all graphs and digraphs, Combinatorica, 6(1) (1986), 73-79.
    3. Eric T. Bax, Algorithms to count paths and cycles, Inf. Process. Lett, 52 (1994), 249-252.
    4. 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.
    5. Eric Bax and Joel Franklin, A finite-difference sieve to count paths and cycles by length, Inf. Process. Lett, 60(4) (1996),171-176.
    6. 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.
    7. Ryan Williams, Finding a path of length k in O (2K) time, Inf. Process. Lett, 109(6) (2009), 315-318.
    8. Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto, Counting paths and packing in halves, Lecture Notes in Computer Science, 5757 (2009), 578-586.
    9. Eric. T. Bax, Inclusion and exclusion algorithm for the Hamiltonian path problem, Inform. Process. Lett. 27(4) (1993),203-207.
    10. A. Bjorklund, T. Husfeldt, P. Kaski, M. Koivisto, The fast intersection transform with applications to counting paths,CoRR, abs/0809.2489 (2008).
    11. J. Chen, S. Lu, S. H. Sze, F. Zhang, Improved algorithms for path, matching and packing problems, 18th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2007), Philadelphia, PA, USA, PP. 298-307. Society for Industrial and Applied Mathematics (2007).
    12. Y. Gurevich, S. Shelah, Expected computation time for Hamiltonian path problem, SIAM J. Comput, 16(1987), 486-502.
    13. I. Koutis, Faster algebraic algorithm for path and packing problems, CALP (2008), LNCS 5125, 575-586, Springer.
    14. D. J. A. Welsh, Complexity: Konts, Colouring and counting, Cambridge University Press, 1993.
    15. Eric. T. Bax, Improvements and bounding for the inclusion and exclusion Hamiltonian algorithm, Caltech-CS-TR-94-11.
    16. B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics, volume 25, (1985), 239-254.
    17. D. Richards, Finding short cycles in a planar graph using separators, Journal of Algorithms, volume 7, (1974), 382-394.
    18. J.A. Bondy and M. Simonovit, Cycles of even length in graphs, Journal of Combinatorial Theory Series B, volume 16,(1974), 97-105.
    19. Lowell W. Beineke and Robin J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, 2007.
    20. F. Harary, Graph Theory, Addison-Wesley, Reading, Mass, 1969.
    21. 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., & Shikare, M. (2014). On the Number of Paths of Lengths 3 and 4 in a Graph. International Journal of Applied Mathematical Research, 3(2), 178-189. https://doi.org/10.14419/ijamr.v3i2.2409

    Received date: 2014-04-10

    Accepted date: 2014-05-09

    Published date: 2014-05-16