Independent dominating sets in graphs of girth five

DOI10.1017/S0963548320000279zbMath1466.05165OpenAlexW3154032260MaRDI QIDQ4993127

Ararat Harutyunyan, Paul S. Horn, Jacques Verstraete

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548320000279

zbMATH Keywords

maximum independent setsemirandom methods

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (2)

A tight bound for independent domination of cubic graphs without 4‐cycles ⋮ On graph fall-coloring: existence and constructions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the independence number of triangle-free graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• On the independence and chromatic numbers of random regular graphs
• On the ratio of optimal integral and fractional covers
• Coloring graphs with sparse neighborhoods
• Large independent sets in regular graphs of large girth
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• On the Independent Domination Number of Random Regular Graphs

This page was built for publication: Independent dominating sets in graphs of girth five