Discrepancy and signed domination in graphs and hypergraphs

A. Poghosyan, V. Zverovich

Research output: Contribution to journalArticlepeer-review

6 Citations (SciVal)


For a graph G, a signed domination function of G is a two-colouring of the vertices of G with colours +1 and -1 such that the closed neighbourhood of every vertex contains more +1's than -1's. This concept is closely related to combinatorial discrepancy theory as shown by Füredi and Mubayi [Z. Füredi, D. Mubayi, Signed domination in regular graphs and set-systems, J. Combin. Theory Ser. B 76 (1999) 223-239]. The signed domination number of G is the minimum of the sum of colours for all vertices, taken over all signed domination functions of G. In this paper, we present new upper and lower bounds for the signed domination number. These new bounds improve a number of known results.

Original languageEnglish
Pages (from-to)2091-2099
Number of pages9
JournalDiscrete Mathematics
Issue number15-16
Publication statusPublished - 28 Aug 2010


  • Graphs
  • Signed domination function
  • Signed domination number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science


Dive into the research topics of 'Discrepancy and signed domination in graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this