The Number of Fixed Length Cycles in Undirected Graph Explicit Formula in Case of Small Lengths

Cover Page

Abstract


Modifications of Ross and Harary algorithm to express the number ck of cycles of length k in an undirected graph in terms of its adjacency matrix are developed. The general undirected graphs as well as bipartite graphs were considered. Computer algebra implementations of the algorithms enable us to construct the formulae at least for k ≤ 12 in general case and for k ≤ 14 in case of bipartite graph. It was shown that, for any fixed value of k ≥ 8 and space complexity quadratic in order n of a graph, the time complexity of computing ck is O(n[k/2] logn). In case of bipartite graph, for k = 8,10,14 better estimations are obtained: O(n3 log2n), O(n4 log2n), O(n6 log2n).

About the authors

A N Voropaev

Petrozavodsk State University

Email: antonvoropaev@mail.ru
Кафедра прикладной математики и кибернетики; Петрозаводский государственный университет; Petrozavodsk State University

S N Perepechko

Petrozavodsk State University

Email: persn@newmail.ru
Кафедра прикладной математики и кибернетики; Петрозаводский государственный университет; Petrozavodsk State University

References

Statistics

Views

Abstract - 240

PDF (Russian) - 120

Cited-By



Copyright (c) 2012 Воропаев А.Н., Перепечко С.Н.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies