Reinforcement numbers of digraphs

Jia Huang, Jian Wei Wang, Jun Ming Xu

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.

Original languageEnglish (US)
Pages (from-to)1938-1946
Number of pages9
JournalDiscrete Applied Mathematics
Volume157
Issue number8
DOIs
StatePublished - Apr 28 2009

Keywords

  • Domination
  • Efficient dominating set
  • Kautz digraphs
  • Private neighbor
  • Reinforcement number
  • de Bruijn digraphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Reinforcement numbers of digraphs'. Together they form a unique fingerprint.

Cite this