An explicit formula for counting k-cycles in graphs is the combination of sums correspondingto the shapes of closed k-walks. It was shown that the maximum multiplicity of a sumin the formula is [k/2] for, starting with k = 8. In this work, we study the maximum summultiplicity for some families of graphs: bipartite, triangle-free, planar, maximum vertexdegree three, and their intersections. When k is large, the biparticity and degree boundednessesare the only properties which decrease the maximum sum multiplicity by 1, providingk = 2, 3 (mod 4). Some combinations of properties in the case of k ^ 20 yield the decreaseby 1 or 2.
Download file
Counter downloads: 75
- Title Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
- Headline Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(14)
- Date:
- DOI
Keywords
prism graphs, shapes of closed walks, counting cycles in graphs, призматические графы, формы замкнутых маршрутов, подсчёт циклов в графахAuthors
References
Papadimitriou C. H. and Yannakakis M. The clique problem for planar graphs // Inform. Processing Lett. 1981. V. 13. No. 4, 5. P. 131-133.
flowproblem.ru/cycles/explicit-formulae/ck-graphs - Ck-graphs: FlowProblem. 2011.
cs.anu.edu.au/~bdm/nauty - The nauty page. 2011.
Харари Ф. Теория графов. М.: Мир, 1973. 301 с.
Воропаев А. Н. Учёт обхвата при подсчёте коротких циклов в двудольных графах // Информационные процессы. 2011. Т. 11. №2. С. 225-252.
Alon N., Yuster R., and Zwick U. Finding and counting given length cycles // Algorithmica. 1997. V. 17. No. 3. P. 209-223.
Perepechko S. N. and Voropaev A. N. The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths // Int. Conf. "Mathematical Modeling and Computational Physics" (MMCP'2009). Dubna: JINR, 2009. P. 148-149.
Harary F. and Manvel B. On the number of cycles in a graph // Matematicky casopis. 1971. V. 21. No. 1. P. 55-63.
Chang Y. C. and Fu H. L. The number of 6-cycles in a graph // The Bulletin of the Institute of Combinatorics and Its Applications. 2003. V. 39. P. 27-30.
Воропаев А.Н. Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах // Информационные процессы. 2011. Т. 11. №1. С. 90-113.
Flum J. and Grohe M. The parameterized complexity of counting problems // SIAM J. Comput. 2004. V.33. No. 4. P. 892-922.
Liskiewicz M., Ogihara M., and Toda S. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes // Theor. Comput. Sci. 2003. V. 304. No. 1-3. P. 129-156.
Valiant L. G. The complexity of enumeration and reliability problems // SIAM J. Comput. 1979. V.8. No. 3. P. 410-421.
Halford T. R. and Chugg K. M. An algorithm for counting short cycles in bipartite graphs // IEEE Trans. Inform. Theory. 2006. V. 52. No. 1. P. 287-292.
Cardillo A., Scellato S., Latora V., and Porta S. Structural properties of planar graphs of urban street patterns // Phys. Rev. E. 2006. V. 73. No. 6. P. 066107(8).
Newman M. E. J. The structure and function of complex networks // SIAM Rev. 2003. V. 45. No. 2. P. 167-256.
Harary F. and Kommel H. J. Matrix measures for transitivity and balance // J. Math. Sociol. 1979. V.6. No. 2. P. 199-210.
Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 4(14).
Download full-text version
Download fileCounter downloads: 212