The method being considered is based on enumeration of the shapes of closed k-walks. Each shape results in a sum involving the elements of the adjacency matrix. Certain combination of these sums evaluates to the number of k-cycles.

For k ≤ 7, it is known that the most time consuming operation in the formula is matrix multiplication. For larger values of k, the complexity of the expression is due to sums of order at least four. In our previous work, we showed that starting with k = 8 the largest order is [k∕2].

Besides general formulae for arbitrary graphs, our approach is capable to produce specific formulae with regard to graph’s particular qualities. In this report, we consider the families of bipartite graphs, triangle-free graphs, planar graphs, graphs with maximum vertex degree 3, and various intersections of these families.

It is shown that for k ≥ 19 the maximum order of sum for specified families is mainly the same as in general case. The exceptions are biparticity and the degree bound cases. In any of these two cases, the maximum order of sum is 2[k∕4]. For the values of k up to 18, there are some exceptions when the order of formula’s complexity is smaller by one or two in comparison with general regularity.

Рассматриваемый в докладе способ подсчёта циклов основан на перечислении форм замкнутых маршрутов фиксированной длины k. Каждой форме соответствует кратная сумма, в которой участвуют элементы матрицы смежности. Комбинация сумм с определёнными коэффициентами даёт выражение для количества циклов длиной k.

Известно, что при k ≤ 7 наиболее трудоёмкой операцией во всей формуле является умножение матриц. При б´ольших значениях длины сложность выражений определяется суммами кратностью не менее четырёх. В нашей предыдущей работе было показано, что начиная со значения k = 8 наибольшая кратность суммы равна [k∕2].

Помимо общих формул для случая произвольных графов предложенный подход позволяет выводить частные формулы с учётом специфики графов. В данном докладе рассматриваются семейства двудольных графов, графов без треугольников, планарных графов, графов со степенями вершин не более трёх, а также различные пересечения этих семейств.

Показано, что при k ≥ 19 на рассматриваемых семействах графов достигается, в основном, та же кратность [k∕2], что и в общем случае. Исключение составляют условие двудольности и ограничение степеней значением три. С учётом какого-либо из этих двух свойств наибольшая кратность равна 2[k∕4]. В диапазоне значений длины цикла до 19 возникает ряд исключений, когда вычислительная сложность формулы оказывается на один или два порядка меньше, чем требует общая закономерность.