Distinguishing Number and Distinguishing Index of the Join of Two Graphs

Document Type : Original Scientific Paper

Authors

Department of Mathematics, Yazd University, Yazd, Iran

Abstract

The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. In this paper we study the distinguishing number and the distinguishing index of the join of two graphs G and H, i.e., G+H. We prove that 0≤ D(G+H)-max{D(G),D(H)}≤ z, where z depends on the number of some induced subgraphs generated by some suitable partitions of V(G) and V(H). Let Gk be the k-th power of G with respect to the join product. We prove that if G is a connected graph of order n ≥ 2, then Gk has the distinguishing index 2, except D'(K2+K2)=3.

Keywords

References

[1] M. O. Albertson, Distinguishing Cartesian powers of graphs, Electron. J. Combin. 12 (2005) #N17, 5 pp.
[2] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18, 1 - 17.
[3] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat 31 (2017) 4393 - 4404.
[4] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29 - 35.
[5] M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math. 308 (2008) 2240 - 2246.
[6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Chapman and Hall/CRC, 2011.
[7] W. Imrich, J. Jerebic and S. Klavžar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (2008) 922 - 929.
[8] R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge-colourings, European J. Combin. 45 (2015) 124 - 131.
[9] S. Klavžar and X. Zhu, Cartesian powers of graphs can be distinguished by two labels, European J. Combin. 28 (2007) 303 - 310.
[10] M. Pilsniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017) 259 - 274.
Mathematics Interdisciplinary Research
Volume 4, Issue 2 - Serial Number 2
December 2019
Pages 239-251

Files

Share

How to cite

Statistics