The absorbant number of generalized de Bruijn digraphs

Jyhmin Kuo, Hung-Lin Fu

Research output: Contribution to journalArticlepeer-review

Abstract

Let D = (V, A) be a digraph with the vertex set V and the arc set A. An absorbant of D is a set S ⊆ V such that for each v ∈ V \ S, O(v) ∩ S ≠ θ where O(v) is the out-neighborhood of v. The absorbant number of D, denoted by γa(D), is denned as the minimum cardinality of an absorbant of D. The generalized de Bruijn digraph GB(n, d) is a digraph with the vertex set V(GB(n, d)) = {0, 1, 2, ..., n-1} and the arc set A(GB(n, d)) = {(x, y)|y = dx + i (mod n), 0 ≤ i < d}. In this paper, we determine γa(GB(n, d)) for all d ≤ n ≤ 4d.

Original languageEnglish
Pages (from-to)433-443
Number of pages11
JournalArs Combinatoria
Volume118
StatePublished - 1 Jan 2015

Keywords

  • Absorbant number
  • Generalized de Bruijn digraph
  • Resource location problem

Fingerprint Dive into the research topics of 'The absorbant number of generalized de Bruijn digraphs'. Together they form a unique fingerprint.

Cite this