An improved upper bound for the bondage number of graphs on surfaces

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

The bondage number b(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. Recently Gagarin and Zverovich showed that, for a graph G with maximum degree Δ(G) and embeddable on an orientable surface of genus h and a non-orientable surface of genus k, b(G)≤minΔ(G)+h+2,Δ+k+1. They also gave examples showing that adjustments of their proofs implicitly provide better results for larger values of h and k. In this paper we establish an improved explicit upper bound for b(G), using the Euler characteristic χ instead of the genera h and k, with the relations χ=2-2h and χ=2-k. We show that b(G)≤Δ(G)+⌊r⌋ for the case χ≤0 (i.e. h<1 or k<2), where r is the largest real root of the cubic equation z3+2 z2+(6χ-7)z+18χ-24=0. Our proof is based on the technique developed by Carlson-Develin and Gagarin-Zverovich, and includes some elementary calculus as a new ingredient. We also find an asymptotically equivalent result b(G)≤Δ(G)+12-6χ-12⌉ for χ≤0, and a further improvement for graphs with large girth.

Original languageEnglish (US)
Pages (from-to)2776-2781
Number of pages6
JournalDiscrete Mathematics
Volume312
Issue number18
DOIs
StatePublished - Sep 28 2012

Keywords

  • Bondage number
  • Euler characteristic
  • Euler's formula
  • Genus
  • Girth
  • Graph embedding

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'An improved upper bound for the bondage number of graphs on surfaces'. Together they form a unique fingerprint.

  • Cite this