Properties of regular graphs with large girth via local algorithms

DOI10.1016/J.JCTB.2016.07.009zbMath1348.05191OpenAlexW2516346504MaRDI QIDQ326821

Carlos Hoppen, Nicholas C. 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)

Related Items (10)

Total domination in regular graphs ⋮ Factor of IID Percolation on Trees ⋮ Properties of regular graphs with large girth via local algorithms ⋮ Asymptotic bounds on total domination in regular graphs ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ Cubic graphs with small independence ratio ⋮ Replica bounds by combinatorial interpolation for diluted spin systems ⋮ Entropy and expansion ⋮ Minimum 2-dominating sets in regular graphs ⋮ Minimum Power Dominating Sets of Random Cubic Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Properties of regular graphs with large girth via local algorithms
• Upper bounds on the bisection width of 3- and 4-regular graphs
• Connected domination of regular graphs
• Large independent sets in random regular graphs
• 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 max and min bisection of random cubic and random 4-regular graphs
• Differential equations for random processes and random graphs
• Bounds on the bisection width for random \(d\)-regular graphs
• Large independent sets in regular graphs of large girth
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Fractional colorings of cubic graphs with large girth
• Colouring Random Regular Graphs
• Girth and Independence Ratio
• On the bipartite density of regular graphs with large girth
• Minimum Power Dominating Sets of Random Cubic Graphs
• Colouring Random 4-Regular Graphs
• Limits of local algorithms over sparse random graphs

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