Document Type : Research Paper

**Authors**

Department of Mathematics, Faculty of Science, Khon Kaen University

**Abstract**

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$.

**Keywords**

**Main Subjects**

[1] E. Abuhijleh, M. Abudayah, O. Alomari and H. Al-Ezeh, Matching number, independence number, and covering

vertex number of Γ(Zn ). Mathematics, 7 (2019) pp. 9.

vertex number of Γ(Zn ). Mathematics, 7 (2019) pp. 9.

[2] R. Akhtar, M. Boggess, T. J. Henderson, I. Jimenez, R. Karpman, A. Kinzel and D. Pritikin, On the unitary Cayley

graph of a finite ring, Electron. J. Combin., 16 (2009) pp. 13.

graph of a finite ring, Electron. J. Combin., 16 (2009) pp. 13.

[3] R. G. Artes and Jr. R. D. Dignos, Tree covers of graphs, Appl. Math. Sci., 8 (2014) 7469–7473.

[4] L. W. Beineke, A survey of packings and coverings of graphs, 1969 The Many Facets of Graph Theory (Proc. Conf.,

Western Mich. Univ., Kalamazoo, Mich.), Springer, Berlin, (1968) 45–53.

Western Mich. Univ., Kalamazoo, Mich.), Springer, Berlin, (1968) 45–53.

[5] L. W. Beineke, Minimal decompositions of complete graphs into subgraphs with embeddability properties, Canadian

J. Math., 21 (1969) 992–1000.

J. Math., 21 (1969) 992–1000.

[6] M. Boggess, T. J. Henderson, I. Jimenez and R. Karpman, The structure of unitary Cayley graphs, SUMSRI. J.,

(2008).

(2008).

[7] G. Chartland and L. Lesniak, Graphs and digraphs (2nd edition), Chapman and Hall, New York, 1996.

[8] L. Chen, X. Li and H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, Graphs

Combin., 29 (2013) 1235–1247.

Combin., 29 (2013) 1235–1247.

[9] I. Dejter and R. E. Giudici, On unitary Cayley graphs, J. Combin. Math. Combin. Comput., 18 (1995) 121–124.

[10] D. S. Dummit and R. M. Foote, Abstract algebra, Third edition, John Wiley & Sons, Inc., Hoboken, NJ, 2004.

[11] Z. Furedi, A. V. Kostochka, R. Skrekovski, M. Stiebitz and D. B. West, Nordhaus-Gaddum type theorems for

decomposition into many parts, J. Graph Theory, 50 (2005) 273–292.

decomposition into many parts, J. Graph Theory, 50 (2005) 273–292.

[12] M. A. Henning, E. J. Joubert and J. Southey, Nordhaus-Gaddum type results for total domination, Discrete Math.

Theoret. Comput. Sci., 13 (2011) 87–95.

Theoret. Comput. Sci., 13 (2011) 87–95.

[13] S. D. Hochbaum and A. Levin, Covering the edges of bipartite graphs using K2,2 graphs, Approximation and online

algorithms, , Lecture Notes in Comput. Sci., 4927, Springer, Berlin, (2008) 116–127.

algorithms, , Lecture Notes in Comput. Sci., 4927, Springer, Berlin, (2008) 116–127.

[14] H. X. Jiang and L. Y. Kang, Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs,

Acta Math. Sin. (Engl. Ser.), 27 (2011) 607–616.

Acta Math. Sin. (Engl. Ser.), 27 (2011) 607–616.

[15] D. Kiani and M. M. H. Aghaei, On the unitary Cayley graph of a ring, Electron. J. Combin., 19 (2012) pp. 10.

[16] W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin., 14 (2007) pp. 12.

[17] K. Knauer and T. Ueckerdt, Three ways to cover a graph, Discrete Math., 339 (2016) 745–758.

[18] W. Li, X. Li, C. Magnant and J. Zhang, Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection

number of graphs, Results Math., 72 (2017) 2079–2100.

number of graphs, Results Math., 72 (2017) 2079–2100.

[19] X. Li and Y. Mao, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Discrete Appl.

Math., 185 (2015) 102–112.

Math., 185 (2015) 102–112.

[20] H. Lin, J. Shu and B. Wu, Nordhaus-Gaddum type result for the matching number of a graph, J. Comb. Optim.,

34 (2017) 916–930.

34 (2017) 916–930.

[21] D. Lu, J. Du, N. Lin, K. Zhang and D. Yi, Nordhaus-Gaddum-type results for path covering and L(2, 1)-labeling

numbers, J. Comb. Optim., 29 (2015) 502–510.

numbers, J. Comb. Optim., 29 (2015) 502–510.

[22] A. Naghipour, The induced subgraph of the unitary Cayley graph of a commutative ring over regular elements,

Miskolc Math. Notes., 17 (2014) 965–977.

Miskolc Math. Notes., 17 (2014) 965–977.

[23] E. A. Nordhaus and J. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956) 175–177.

[24] L. Pyber, Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B, 66 (1996) 152–159.

[25] I. Shirakawa, H. Takahashi and H. Ozaki, On the decomposition of a complete graph into planar subgraphs, J.

Franklin Inst., 283 (1967) 379–388.

Franklin Inst., 283 (1967) 379–388.

[26] D. B. West, Introduction to graph theory (2nd edition), Pearson Education Pte. Ltd., Singapore, 2001.

[27] N. Williams, Decomposition of finite graphs into forest, J. Lond. Math. Soc., 39 (1964).

June 2022

Pages 111-122

**Receive Date:**30 December 2020**Revise Date:**25 September 2021**Accept Date:**23 October 2021**Published Online:**01 June 2022