Premium
A new domination conception
Author(s) -
Stracke Christoph,
Volkmann Lutz
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170306
Subject(s) - combinatorics , dominating set , domination analysis , mathematics , vertex (graph theory) , graph , simple graph , integer (computer science) , order (exchange) , cardinality (data modeling) , discrete mathematics , finance , computer science , economics , data mining , programming language
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. 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.