The bondage numbers of graphs with small crossing numbers

Jia Huang, Jun Ming Xu

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

The bondage number b (G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ (G) of G. Kang and Yuan proved b (G) ≤ 8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.

Original languageEnglish (US)
Pages (from-to)1881-1897
Number of pages17
JournalDiscrete Mathematics
Volume307
Issue number15
DOIs
StatePublished - Jul 6 2007

Keywords

  • Bondage number
  • Crossing number
  • Domination number
  • Planar graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The bondage numbers of graphs with small crossing numbers'. Together they form a unique fingerprint.

  • Cite this