Geodesic
Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 42-55.

Voir la notice de l'article provenant de la source Math-Net.Ru

An explicit formula for counting $k$-cycles in graphs is the combination of sums corresponding to the shapes of closed $k$-walks. It was shown that the maximum multiplicity of a sum in the formula is $[k/2]$ for, starting with $k=8$. In this work, we study the maximum sum multiplicity for some families of graphs: bipartite, triangle-free, planar, maximum vertex degree three, and their intersections. When $k$ is large, the biparticity and degree boundednesses are the only properties which decrease the maximum sum multiplicity by 1, providing $k\equiv2,3\pmod4$. Some combinations of properties in the case of $k\leq20$ yield the decrease by 1 or 2.
Keywords: counting cycles in graphs, shapes of closed walks, prism graphs. 
@article{PDM_2011_4_a5,
     author = {A. N. Voropaev},
     title = {Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {42--55},
     publisher = {mathdoc},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_4_a5/}
}
TY  - JOUR
AU  - A. N. Voropaev
TI  - Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 42
EP  - 55
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_4_a5/
LA  - ru
ID  - PDM_2011_4_a5
ER  - 
%0 Journal Article
%A A. N. Voropaev
%T Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 42-55
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_4_a5/
%G ru
%F PDM_2011_4_a5
A. N. Voropaev. Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs. Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 42-55. http://geodesic.mathdoc.fr/item/PDM_2011_4_a5/

[1] Harary F., Kommel H. J., “Matrix measures for transitivity and balance”, J. Math. Sociol., 6:2 (1979), 199–210 | DOI | MR | Zbl

[2] Newman M. E. J., “The structure and function of complex networks”, SIAM Rev., 45:2 (2003), 167–256 | DOI | MR | Zbl

[3] Cardillo A., Scellato S., Latora V., Porta S., “Structural properties of planar graphs of urban street patterns”, Phys. Rev. E, 73:6 (2006), 066107, 8 pp. | DOI

[4] Halford T. R., Chugg K. M., “An algorithm for counting short cycles in bipartite graphs”, IEEE Trans. Inform. Theory, 52:1 (2006), 287–292 | DOI | MR

[5] Valiant L. G., “The complexity of enumeration and reliability problems”, SIAM J. Comput., 8:3 (1979), 410–421 | DOI | MR | Zbl

[6] Liśkiewicz M., Ogihara M., Toda S., “The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes”, Theor. Comput. Sci., 304:1–3 (2003), 129–156 | DOI | MR | Zbl

[7] Flum J., Grohe M., “The parameterized complexity of counting problems”, SIAM J. Comput., 33:4 (2004), 892–922 | DOI | MR | Zbl

[8] Voropaev A. N., “Vyvod yavnykh formul dlya podschëta tsiklov fiksirovannoi dliny v neorientirovannykh grafakh”, Informatsionnye protsessy, 11:1 (2011), 90–113

[9] Harary F., Manvel B., “On the number of cycles in a graph”, Matematický časopis, 21:1 (1971), 55–63 | MR | Zbl

[10] Chang Y. C., Fu H. L., “The number of 6-cycles in a graph”, The Bulletin of the Institute of Combinatorics and Its Applications, 39 (2003), 27–30 | MR | Zbl

[11] Perepechko S. N., 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), JINR, Dubna, 2009, 148–149

[12] Alon N., Yuster R., Zwick U., “Finding and counting given length cycles”, Algorithmica, 17:3 (1997), 209–223 | DOI | MR | Zbl

[13] Voropaev A. N., “Uchët obkhvata pri podschëte korotkikh tsiklov v dvudolnykh grafakh”, Informatsionnye protsessy, 11:2 (2011), 225–252 | MR

[14] Kharari F., Teoriya grafov, Mir, M., 1973, 301 pp. | MR

[15] Ck-graphs: FlowProblem, 2011 http://flowproblem.ru/cycles/explicit-formulae/ck-graphs

[16] The nauty page, 2011 http://cs.anu.edu.au/~bdm/nauty

[17] Papadimitriou C. H., Yannakakis M., “The clique problem for planar graphs”, Inform. Processing Lett., 13:4–5 (1981), 131–133 | DOI | MR