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

Pongpipat, Denpong; Nupo, Nuttawoot

doi:10.22108/toc.2021.126721.1802

تعداد نشریات	43
تعداد شماره‌ها	1,706
تعداد مقالات	13,973
تعداد مشاهده مقاله	33,628,948
تعداد دریافت فایل اصل مقاله	13,339,662

	Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings
Transactions on Combinatorics
دوره 11، شماره 2، شهریور 2022، صفحه 111-122 اصل مقاله (253.04 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2021.126721.1802
نویسندگان
Denpong Pongpipat؛ Nuttawoot Nupo^*
Department of Mathematics, Faculty of Science, Khon Kaen University
چکیده
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$‎.
کلیدواژه‌ها
‎Nordhaus-Gaddum type inequalities‎؛ ‎Unitary Cayley graph‎؛ ‎Tree cover‎؛ ‎Tree covering number

مراجع
[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).
آمار تعداد مشاهده مقاله: 793 تعداد دریافت فایل اصل مقاله: 960

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

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