Relations between the distinguishing number and some other graph parameters

Document Type : Research Paper

Authors

Department of Mathematics, Shiraz University, P.O.Box 71964-84334, Shiraz, Iran

Abstract

A distinguishing coloring of a simple graph $G$ is a vertex coloring of $G$ which is preserved only by the identity automorphism of $G$. In other words, this coloring ``breaks'' all symmetries of $G$. The distinguishing number $D(G)$ of a graph $G$ is defined to be the smallest number of colors in a distinguishing coloring of $G$. This concept of “symmetry breaking” was first proposed by Babai in 1977 and after the publication of a seminal paper by Albertson in 1996, it attracted the attention of many mathematicians. In this paper, along with studying some relations between $D(G)$ and some other important graph parameters, we introduce the concept of a $(D,\alpha)$-ordinary graph which displays the comparison between $D(G)$ and the independence number $\alpha(G)$. Then we consider the classification of $(D,\alpha)$-ordinary graphs in various families of graphs such as forests, cycles, generalized Johnson graphs, Cartesian products of graphs and line graphs of connected claw-free graphs. We also propose some conjectures and discuss about some future research directions in this topic.

Keywords

References

[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.
Mathematics and Society
Volume 9, Issue 3 - Serial Number 3
September 2024
Pages 73-92

Files

History

  • Receive Date: 02 July 2023
  • Revise Date: 06 March 2024
  • Accept Date: 09 March 2024
  • Publish Date: 16 November 2024

Share

How to cite

Statistics