TY - JOUR

T1 - The integer { k } -domination number of circulant graphs

AU - Cheng, Yen Jen

AU - Fu, Hung Lin

AU - Liu, Chia An

PY - 2020/1/1

Y1 - 2020/1/1

N2 - Let G = (V,E) be a simple undirected graph. G is a circulant graph defined on V = &n with difference set D 1, 2,;hellip&,n 2 provided two vertices i and j in ;n are adjacent if and only if min{|i - j|,n -|i - j|} D. For convenience, we use G(n; D) to denote such a circulant graph. A function f: V (G) → 0 is an integer {k}-domination function if for each v V (G), u NG[v]f(u) ≥ k. By considering all {k}-domination functions f, the minimum value of v V (G)f(v) is the {k}-domination number of G, denoted by γk(G). In this paper, we prove that if D = {1, 2,...,t}, 1 ≤ t ≤ n-1 2, then the integer {k}-domination number of G(n; D) is kn 2t+1.

AB - Let G = (V,E) be a simple undirected graph. G is a circulant graph defined on V = &n with difference set D 1, 2,;hellip&,n 2 provided two vertices i and j in ;n are adjacent if and only if min{|i - j|,n -|i - j|} D. For convenience, we use G(n; D) to denote such a circulant graph. A function f: V (G) → 0 is an integer {k}-domination function if for each v V (G), u NG[v]f(u) ≥ k. By considering all {k}-domination functions f, the minimum value of v V (G)f(v) is the {k}-domination number of G, denoted by γk(G). In this paper, we prove that if D = {1, 2,...,t}, 1 ≤ t ≤ n-1 2, then the integer {k}-domination number of G(n; D) is kn 2t+1.

KW - Circulant graph

KW - Euclidean algorithm

KW - integer linear program

KW - integer { k } -domination number

UR - http://www.scopus.com/inward/record.url?scp=85085699410&partnerID=8YFLogxK

U2 - 10.1142/S179383092050055X

DO - 10.1142/S179383092050055X

M3 - Article

AN - SCOPUS:85085699410

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

SN - 1793-8309

ER -