Domination ratio of a family of integer distance digraphs with arbitrary degree

Research output: Contribution to journalArticlepeer-review

Abstract

An integer distance digraph is the Cayley graph Γ(Z,S) of the additive group Z of all integers with respect to a finite subset S⊆Z. The domination ratio of Γ(Z,S), defined as the minimum density of its dominating sets, is related to some number theory problems, such as tiling the integers and finding the maximum density of a set of integers with missing differences. We precisely determine the domination ratio of the integer distance graph Γ(Z,{1,2,…,d−2,s}) for any integers d and s satisfying d≥2 and s∉[0,d−2]. Our result generalizes a previous result on the domination ratio of the graph Γ(Z,{1,s}) with s∈Z∖{0,1} and also implies the domination number of certain circulant graphs Γ(Zn,S), where Zn is the finite cyclic group of integers modulo n and S is a subset of Zn.

Original languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalDiscrete Applied Mathematics
Volume317
DOIs
StatePublished - Aug 15 2022

Keywords

  • Cayley graph
  • Circulant graph
  • Domination ratio
  • Efficient dominating set
  • Integer distance graph
  • Integer tiling

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Domination ratio of a family of integer distance digraphs with arbitrary degree'. Together they form a unique fingerprint.

Cite this