Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420576 | Discrete Applied Mathematics | 2009 | 9 Pages |
Abstract
The reinforcement number of a graph GG 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 GG. 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jia Huang, Jian-Wei Wang, Jun-Ming Xu,