|
Prikladnaya Diskretnaya Matematika, 2011, Number 4(14), Pages 42–55
(Mi pdm350)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Graph Theory
Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs
A. N. Voropaev Petrozavodsk State University, Petrozavodsk, Russia
Abstract:
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.
Citation:
A. N. Voropaev, “Multiplicities of sums in the explicit formulae for counting fixed length cycles in undirected graphs”, Prikl. Diskr. Mat., 2011, no. 4(14), 42–55
Linking options:
https://www.mathnet.ru/eng/pdm350 https://www.mathnet.ru/eng/pdm/y2011/i4/p42
|
Statistics & downloads: |
Abstract page: | 315 | Full-text PDF : | 115 | References: | 49 |
|