TY - JOUR
T1 - Properties of regular graphs with large girth via local algorithms
AU - Hoppen, Carlos
AU - Wormald, Nicholas
PY - 2016/11/1
Y1 - 2016/11/1
N2 - 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.
AB - 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.
KW - Large-girth graphs
KW - Local algorithms
KW - Random regular graphs
UR - http://www.scopus.com/inward/record.url?scp=84991571980&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2016.07.009
DO - 10.1016/j.jctb.2016.07.009
M3 - Article
AN - SCOPUS:84991571980
VL - 121
SP - 367
EP - 397
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
SN - 0095-8956
ER -