Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings

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

References

[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.
[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.
[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.
[5] L. W. Beineke, Minimal decompositions of complete graphs into subgraphs with embeddability properties, Canadian
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).
[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.
[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.
[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.
[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.
[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.
[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.
[19] X. Li and Y. Mao, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Discrete Appl.
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.
[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.
[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.
[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.
[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).

Files

Cited by

History

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

Share

How to cite

Statistics