Domination number of graphs with minimum degree five

2019/12/31 by Bujtás, Csilla · 1 citation
#05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1912.13499

Abstract

We prove that for every graph G on n vertices and with minimum degree five, the domination number γ(G) cannot exceed n/3. The proof combines an algorithmic approach and the discharging method. Using the same technique, we provide a shorter proof for the known upper bound 4n/11 on the domination number of graphs of minimum degree four.

Cited by

• On the isolation number of graphs with minimum degree four

Related

• Improved upper bounds on the domination number of graphs with minimum degree at least five
• On the game domination number of graphs with given minimum degree
• The sub-k-domination number of a graph with applications to k-domination
• General upper bound on the game domination number
• Graphs with equal domination and certified domination numbers