The integer { k } -domination number of circulant graphs

Yen Jen Cheng, Hung Lin Fu, Chia An Liu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
JournalDiscrete Mathematics, Algorithms and Applications
StateAccepted/In press - 1 Jan 2020


  • Circulant graph
  • Euclidean algorithm
  • integer linear program
  • integer { k } -domination number

Fingerprint Dive into the research topics of 'The integer { k } -domination number of circulant graphs'. Together they form a unique fingerprint.

Cite this