Random walks and bisections in random circulant graphs

Bernard Mans*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Citation (Scopus)


Using number theoretical tools, we prove two main results for random r-regular circulant graphs with n vertices, when n is sufficiently large and r is fixed. First, for any fixed ε > 0, prime n and L ≥ n 1/r (logn) 1+1/r+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm to find a vertex bisector and an edge bisector, both of size less than n 1-1/r+o(1). As circulant graphs are popular network topologies in distributed computing, we show that our results can be exploited for various information dissemination schemes. In particular, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. This settles an open question in an earlier work of the authors (2004) and shows that the generic gossiping algorithms of that work are nearly optimal.

Original languageEnglish
Title of host publicationLATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings
EditorsDavid Fernández-Baca
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Number of pages14
ISBN (Print)9783642293436
Publication statusPublished - 2012
Event10th Latin American Symposiumon Theoretical Informatics, LATIN 2012 - Arequipa, Peru
Duration: 16 Apr 201220 Apr 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7256 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other10th Latin American Symposiumon Theoretical Informatics, LATIN 2012


Dive into the research topics of 'Random walks and bisections in random circulant graphs'. Together they form a unique fingerprint.

Cite this