adv

adv

Domination and Upper Domination of Direct Product Graphs. (arXiv:1708.01305v1 [math.CO])

The unitary Cayley graph of $\mathbb{Z} /n \mathbb{Z}$, denoted $X_{\mathbb{Z} / n \mathbb{Z}}$, has vertices $0,1, \dots, n-1$ with $x$ adjacent to $y$ if $x-y$ is relatively prime to $n$. We present results on the tightness of the known inequality $\gamma(X_{\mathbb{Z} / n \mathbb{Z}})\leq \gamma_t(X_{\mathbb{Z} / n \mathbb{Z}})\leq g(n)$, where $\gamma$ and $\gamma_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal's function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma(X_{\mathbb{Z} / n \mathbb{Z}})\leq\gamma_t(X_{\mathbb{Z} / n \mathbb{Z}})\leq g(n)-1$. Extending work of Meki\v{s}, we give lower bounds for the domination numbers of direct products of complete graphs. We also present a simple conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs and prove the conjecture in ce查看全文

Solidot 文章翻译

你的名字

留空匿名提交
你的Email或网站

用户可以联系你
标题

简单描述
内容