Properties of regular graphs with large girth via local algorithms

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.