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

preprint2022arXivOpen access

Abstract

An integer distance digraph is the Cayley graph Γ(Z,S)Γ(\mathbb{Z},S) of the additive group Z\mathbb{Z} of all integers with respect to a finite subset S⊆ZS\subseteq\mathbb{Z}. The domination ratio of Γ(Z,S)Γ(\mathbb{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})Γ(\mathbb{Z},\{1,2,\ldots,d-2,s\}) for any integers dd and ss satisfying d≥2d\ge2 and s∉[0,d−2]s\notin[0,d-2]. Our result generalizes a previous result on the domination ratio of the graph Γ(Z,{1,s})Γ(\mathbb{Z},\{1,s\}) with s∈Z∖{0,1}s\in\mathbb{Z}\setminus\{0,1\} and also implies the domination number of certain circulant graphs Γ(Zn,S)Γ(\mathbb{Z}_n,S), where Zn\mathbb{Z}_n is the finite cyclic group of integers modulo nn and SS is a subset of Zn\mathbb{Z}_n.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.