On integer domination in graphs and Vizing-like problems

Boštjan Brešar, Michael A. Henning, Sandi Klavžar

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

Abstract

We continue the study of {k}-dominating functions in graphs (or integer domination as we shall also say) started by Domke, Hedetniemi, Laskar, and Fricke [5]. For k ≥ 1 an integer, a function f: V(G) → {0, 1,..., k} defined on the vertices of a graph G is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its function values over all vertices. The {k}-domination number of G is the minimum weight of a {k}-dominating function of G. We study the {k}-domination number on the Cartesian product of graphs, mostly on problems related to the famous Vizing's conjecture. A connection between the {k}-domination number and other domination type parameters is also studied.

Original languageEnglish
Pages (from-to)1316-1328
Number of pages13
JournalTaiwanese Journal of Mathematics
Volume10
Issue number5
DOIs
Publication statusPublished - 2006
Externally publishedYes

Keywords

  • Cartesian product
  • Integer domination
  • Vizing's conjecture
  • {k}-dominating function

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On integer domination in graphs and Vizing-like problems'. Together they form a unique fingerprint.

Cite this