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

Jia Huang, Jian Shen

Research output: Contribution to journalArticle

Abstract

The bondage number 6(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. Let G be embeddable on a surface whose Euler characteristic χ is as large as possible, and assume χ < 0. Gagarin-Zverovich and Huang have recently found upper bounds of 6(G) in terms of the maximum degree Δ(G) and the Euler characteristic x-In this paper we prove a better upper bound 6(G) ≤ Δ(G) + [t] where t is the largest real root of the cubic equation z3 + z2 + (3χ -8)z + 9x - 12 = 0; this upper bound is asymptotically equivalent to 6(G) ≤ A(G) + 1. We also establish further improved upper bounds for 6(G) when the girth, order, or size of the graph G is large compared with |χ|.

Original languageEnglish (US)
Pages (from-to)373-387
Number of pages15
JournalArs Combinatoria
Volume140
StatePublished - Jul 2018

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'New upper bounds for the bondage number of a graph in terms of its maximum degree and euler characteristic'. Together they form a unique fingerprint.

  • Cite this