Properties of regular graphs with large girth via local algorithms

Carlos Hoppen, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

The average-case analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. Recently, the authors obtained a general transfer result which translates such bounds into (deterministic) results about all regular graphs with sufficiently large girth. In this paper, we apply this methodology to obtain new upper or lower bounds on the size of maximum independent sets and power dominating sets in cubic graphs with large girth, and maximum cuts, maximum and minimum bisections, and minimum connected and weakly-connected dominating sets in r-regular graphs with large girth. All the new bounds improve upon the best previous bounds. For independent sets in cubic graphs, this also improves on the best “almost sure” bounds for random cubic graphs.

Original languageEnglish
Pages (from-to)367-397
Number of pages31
JournalJournal of Combinatorial Theory, Series B
Volume121
DOIs
Publication statusPublished - 1 Nov 2016

Keywords

  • Large-girth graphs
  • Local algorithms
  • Random regular graphs

Cite this