Properties of regular graphs with large girth via local algorithms

DOI10.1016/J.JCTB.2016.07.009MaRDI QIDQ326821zbMATH OpenOpenAlexFDO

Authors Carlos Hoppen, Nicholas Wormald

Publication date 12 October 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2016.07.009

zbMATH Keywords

random regular graphslarge-girth graphslocal algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12)

Recommendations

• Local algorithms, regular graphs of large girth, and random regular graphs
• Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach
• Large independent sets in regular graphs of large girth
• Large independent sets in random regular graphs
• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Analysis of greedy algorithms on graphs with bounded degrees
• Bounds on the bisection width for random \(d\)-regular graphs
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Colouring Random 4-Regular Graphs
• Colouring Random Regular Graphs
• Connected domination of regular graphs
• Differential equations for random processes and random graphs
• Fractional colorings of cubic graphs with large girth
• Girth and Independence Ratio
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Large independent sets in random regular graphs
• Large independent sets in regular graphs of large girth
• Limits of local algorithms over sparse random graphs
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Minimum power dominating sets of random cubic graphs
• On the bipartite density of regular graphs with large girth
• Properties of regular graphs with large girth via local algorithms
• Upper bounds on the bisection width of 3- and 4-regular graphs

Cited in

(16)

• \(r\)-regular \(r\)-connected graphs with large girth
• Asymptotic bounds on total domination in regular graphs
• Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach
• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth
• Factor of iid percolation on trees
• Entropy and expansion
• Properties of regular graphs with large girth via local algorithms
• Minimum 2-dominating sets in regular graphs
• Cubic graphs with small independence ratio
• Total domination in regular graphs
• Replica bounds by combinatorial interpolation for diluted spin systems
• PROPERTY A AND GRAPHS WITH LARGE GIRTH
• Minimum power dominating sets of random cubic graphs
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Greedy maximal independent sets via local limits
• Local algorithms, regular graphs of large girth, and random regular graphs

This page was built for publication: Properties of regular graphs with large girth via local algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326821)