Discrepancy and Signed Domination in Graphs and Hypergraphs - Mathematics > CombinatoricsReport as inadecuate




Discrepancy and Signed Domination in Graphs and Hypergraphs - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: For a graph G, a signed domination function of G is a two-colouring of thevertices of G with colours +1 and -1 such that the closed neighbourhood ofevery vertex contains more +1-s than -1-s. This concept is closely related tocombinatorial discrepancy theory as shown by Fueredi and Mubayi J. Combin.Theory, Ser. B 76 1999 223-239. The signed domination number of G is theminimum of the sum of colours for all vertices, taken over all signeddomination functions of G. In this paper, we present new upper and lower boundsfor the signed domination number. These new bounds improve a number of knownresults.



Author: A. Poghosyan, V. Zverovich

Source: https://arxiv.org/







Related documents