روابطی بین عدد تشخیص و پارامترهای دیگر گراف‌ها

نوع مقاله : مقاله پژوهشی

نویسندگان

بخش ریاضی، دانشکده علوم، دانشگاه شیراز، شیراز، ایران

چکیده

یک رنگ‌آمیزی تشخیص از گرافی ساده مانند $G$، عبارت است از یک رنگ‌آمیزی رئوس $G$ به‌طوری‌که تنها خودریختی‌ای از $G$ که این رنگ‌آمیزی را حفظ می‌کند، خودریختی همانی باشد. به‌عبارت‌دیگر، این رنگ‌آمیزی همه‌ی تقارن‌های $G$ را «می‌شکند». عدد تشخیص یک گراف مانند $G$، که با $D(G)$
نمایش داده می‌شود، کوچک‌ترین تعداد رنگ مورد نیاز برای یک رنگ‌آمیزی تشخیص~$G$ است. در این مقاله، علاوه بر مطالعه‌ی برخی از روابط موجود بین $D(G)$ و پارامترهای مهم گرافی، مفهوم $(D,\alpha)$-عادی بودن یک گراف را تعریف می‌کنیم که بیانگر مقایسه‌ی بین $D(G)$ و عدد استقلال $\alpha(G)$ است. سپس طیف وسیعی از گراف‌ها را از دیدگاه $(D,\alpha)$-عادی بودن مطالعه و رده‌بندی‌هایی را برای گراف‌های دوبخشی، چندبخشی کامل، گراف‌های جانسون تعمیم‌یافته و حاصل‌ضرب‌های دکارتی و گراف‌های خط برخی از گراف‌ها ارائه می‌کنیم.

کلیدواژه‌ها


[1] B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math., 343 no. 9 (2020) 13 pp.
[2] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin., 3 no. 1 (1996) 17 pp.
[3] S. Alikhani and S. Soltani, The distinguishing number and the distinguishing index of line and graphoidal graph(s), AKCE Int. J. Graphs Comb., 17 no. 1 (2020) 1–6.
[4] Bondy, J., Murty, U. & Others Graph theory with applications. (Macmillan London,1976)
[5] B. Bogstad, and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math., 283 no. 1-3 (2004) 29–35.
[6] K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin., 13 no. 1 (2006) 19 pp.
[7] M. N. Ellingham and J. Z. Schroeder, Distinguishing partitions and asymmetric uniform hypergraphs, Ars Math. Contemp., 4 no. 1 (2011) 111–123.
[8] D. Erwin and F. Harary, Destroying automorphisms by fixing nodes, Discrete Math., 306 no. 24 (2006) 3244–3252. [9] E. Estaji, W. Imrich, R. Kalinowski, M. Pilśniak and T. Tucker, Distinguishing Cartesian products of countable graphs, Discuss. Math. Graph Theory, 37 no. 1 (2017) 155–164.
[10] R. H. Hammack, W. Imrich and S. Klavžar, Product graphs: structure and recognition, Publisher: John Wiley & Sons. Inc., New York,2000.
[11] R. L. Hemminger, The group of an X-join of graphs, J. Combinatorial Theory, 5 (1968) 408–418.
[12] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory, 53 no. 3 (2006) 250–260. [13] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of complete graphs, European J. Combin., 29 no. 4 (2008) 922–929.
[14] W. Imrich, R. Kalinowski, F. Lehner and M. Pilśniak, Endomorphism breaking in graphs, Electron. J. Combin., 21 no. 1(2014) 13 pp.
[15] W. Imrich, S. Klavžar and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin., 14 no. 1 (2007) 12 pp.
[16] R. Kalinowski M. Pilśniak, Distinguishing graphs by edge-colourings, European J. Combin., 45 (2015) 124–131.
[17] R. Kalinowski, M. Pilśniak and M. Woźniak, Distinguishing graphs by total colourings, Ars Math. Contemp., 11 no. 1 (2016) 79–89.
[18] S. Klavžar, T.-L. Wong and X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra, 303 no. 2 (2006) 626–641.
[19] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin., 28 no. 1 (2007) 303–310.
[20] C. Laflamme, L. Thé and N. Sauer, Distinguishing number of countable homogeneous relational structures, Electron. J. Combin., 17 no. 1 (2010) 17 pp.
[21] S. Martin, J. S. Powell and D. F. Rall, On the independence number of the Cartesian product of caterpillars, Ars Combin., 60 (2001) 73–84.
[22] M. Pilsniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp., 13 no. 2 (2017) 259–274. [23] X. Pu, T. Cao, X. Zhang, X. Dong and S. Chen, Learning to learn graph topologies. Proceedings of the 35th International Conference on Neural Information Processing Systems, Article no. 325 (2021) 4249–4262.
[24] H. Schreiber, S. Hüning, J. Kloas, W. Imrich and T. Tucker, Distinguishing locally finite trees, The Australasian Journal Of Combinatorics, (2018).
[25] M. H. Shekarriz, B. Ahmadi, S. A. Talebpour and M. H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory, 103 no. 2 (2023) 359–377.
[26] D. Sitton, Maximum matchings in complete multipartite graphs, Furman University Electronic J. Undergraduate Math., 2 (1996) 6-16.
[27] T. W. Tucker, Distinguishing maps, Electron. J. Combin., 18 no. 1 (2011) 21 pp.
[28] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin., 11 no. 1 (2004) 13 pp.