solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看950次
Domination and Upper Domination of Direct Product Graphs. (arXiv:1708.01305v1 [math.CO])
来源于:arXiv
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 查看全文>>