New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic

preprint2020arXivOpen access

Abstract

The bondage number b(G)b(G) of a graph GG is the smallest number of edges whose removal from GG results in a graph with larger domination number. Let GG be embeddable on a surface whose Euler characteristic χχ is as large as possible, and assume χ≤0χ\leq0. Gagarin-Zverovich and Huang have recently found upper bounds of b(G)b(G) in terms of the maximum degree Δ(G)Δ(G) and the Euler characteristic χ(G)=χχ(G)=χ. In this paper we prove a better upper bound b(G)≤Δ(G)+⌊t⌋b(G)\leqΔ(G)+\lfloor t\rfloor where tt is the largest real root of the cubic equation z3+z2+(3χ−8)z+9χ−12=0z^3 + z^2 + (3χ- 8)z + 9χ- 12=0; this upper bound is asymptotically equivalent to b(G)≤Δ(G)+1+⌊4−3χ⌋b(G)\leqΔ(G)+1+\lfloor \sqrt{4-3χ} \rfloor. We also establish further improved upper bounds for b(G)b(G) when the girth, order, or size of the graph GG is large compared with its Euler characteristic χχ.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.