TY - JOUR
ID - 26053
TI - Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Pongpipat, Denpong
AU - Nupo, Nuttawoot
AD - Department of Mathematics, Faculty of Science, Khon Kaen University
Y1 - 2022
PY - 2022
VL - 11
IS - 2
SP - 111
EP - 122
KW - Nordhaus-Gaddum type inequalities
KW - Unitary Cayley graph
KW - Tree cover
KW - Tree covering number
DO - 10.22108/toc.2021.126721.1802
N2 - The unitary Cayley graph $\Gamma_n$ of a finite ring $\mathbb{Z}_n$ is the graph with vertex set $\mathbb{Z}_n$ and two vertices $x$ and $y$ are adjacent if and only if $x-y$ is a unit in $\mathbb{Z}_n$. A family $\mathcal{F}$ of mutually edge disjoint trees in $\Gamma_n$ is called a tree cover of $\Gamma_n$ if for each edge $e\in E(\Gamma_n)$, there exists a tree $T\in\mathcal{F}$ in which $e\in E(T)$. The minimum cardinality among tree covers of $\Gamma_n$ is called a tree covering number and denoted by $\tau(\Gamma_n)$. In this paper, we prove that, for a positive integer $ n\geq 3 $, the tree covering number of $ \Gamma_n $ is $ \displaystyle\frac{\varphi(n)}{2}+1 $ and the tree covering number of $ \overline{\Gamma}_n $ is at most $ n-p $ where $ p $ is the least prime divisor of $n$. Furthermore, we introduce the Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of rings $\mathbb{Z}_n$.
UR - https://toc.ui.ac.ir/article_26053.html
L1 - https://toc.ui.ac.ir/article_26053_1faba403cd1999945cf2ce36fbe484ef.pdf
ER -