K-Subdomination in graphs

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f: V→{-1,1} such that ∑u∈N G[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ ks(G), is the minimum of ∑ v∈Vf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ ks(G), the signed domination number γ s(G) and the majority domination number γ maj(G).

Original languageEnglish
Pages (from-to)55-60
Number of pages6
JournalDiscrete Applied Mathematics
Volume120
Issue number1-3
DOIs
StatePublished - 15 Aug 2002

Keywords

  • Domination
  • k-subdomination
  • Leaf
  • Majority domination
  • Signed domination
  • Tree

Fingerprint

Dive into the research topics of 'K-Subdomination in graphs'. Together they form a unique fingerprint.

Cite this