Domination number of cubic graphs with large girth

2009/07/07 by Daniel Kral, Kral, Daniel, Petr Skoda +3 · 1 citation
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69

paper · pdf · doi:10.48550/arxiv.0907.1166

arxiv created 2009/07/07 · arxiv updated 2009/12/01

Abstract

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).

Cited by

• Engineering Dominating Patterns: A Fine-grained Case Study

Related

• Domination of subcubic planar graphs with large girth
• The 1/3-conjectures for domination in cubic graphs
• Lower Bounds for the Domination Numbers of Connected Graphs without Short Cycles
• Cubic Graphs with Total Domatic Number at Least Two
• An approach to the girth problem in cubic graphs