A new domination conception

✍ Scribed by Christoph Stracke; Lutz Volkmann

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 287 KB
• Volume: 17
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190170306

✦ Synopsis

Abstract

Let f be an integer valued function defined on the vertex set V(G) of a simple graph G. We call a subset D~f~ of V(G) a f‐dominating set of G if |N(x, G) ∩ D~f~| ≥ f(x) for all x ∈ V(G) — D~f~, where N(x, G) is the set of neighbors of x. D~f~ is a minimum f‐dominating set if G has no f‐dominating set D′~f~ with |D~f~| < |D~f~|. If j, k ∈ N~0~ = {0,1,2,…} with j ≤ k, then we define the integer valued function f~j,k~ on V(G) by
equation image
.

By μ~j,k~(G) we denote the cardinality of a minimum f~j,k~‐dominating set of G.

A set D ⊆ V(G) is j‐dominating if every vertex, which is not in D, is adjacent to at least j vertices of D. The j‐domination number γ~j~(G) is the minimum order of a j‐dominating set in G.

In this paper we shall give estimations of the new domination number μ~j,k~(G), and with the help of these estimations we prove some new and some known upper bounds for the j‐domination number. © 1993 John Wiley & Sons, Inc.