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

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