Distinguishing index of Kronecker product of two graphs
Abstract
The distinguishing index D'(G) of a graph G is the least integer d such that G has an edge labeling with d labels that is preserved only by a trivial automorphism. The Kronecker product G x H of two graphs G and H is the graph with vertex set V(G) x V(H) and edge set {{(u,x), (v,y)} |{u,v} ∈ E(G) and {x,y} ∈ E(H)}. In this paper we study the distinguishing index of Kronecker product of two graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614//ejgta.2021.9.1.7
References
M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), R18.
S. Alikhani and S. Soltani, The distinguishing number of Kronecker product of two graphs, ICTCSDM 2016, LNCS 10398 (2017), 341-346.
S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat, 31:14 (2017), 4393-4404.
S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of lexicographic product of two graphs, Discuss. Math. Graph Theory 38 (2018), 853-865.
V. Arvind and N. Devanur, Symmetry breaking in trees and planar graphs by vertex coloring, In Proceedings of the Nordic Combinatorial Conference, 2004.
C. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin., 13 (2006), R11.
K.L. Collins and A.N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), R16.
K. Culik, Zur theorie der graphen, Casopis Pest. Mat. 83 (1958), 135–155.
A. Gorzkowska, R. Kalinowski, and M. Pil´sniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contem., 12 (2017), 77–87.
R. Hammack, W. Imrich and S. Klaˇvzar, Handbook of product graphs (second edition), Taylor & Francis group (2011).
W. Imrich, Automorphismen und das kartesische Produkt von Graphen, O sterreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 177 (1969), 203–214.
W. Imrich, J. Jerebic and S. Klavzar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (4), (2008), 922–929.
W. Imrich and S. Klavzar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53.3 (2006), 250–260.
P.K. Jha, Kronecker products of paths and cycles: Decomposition, factorization and bipancyclicity, Discrete Math. 182 (1), (1998), 153–167.
R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015), 124–131.
R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971), 59–101.
D.J. Miller, The automorphism group of a product of graphs, Proc. Amer. Math. Soc. 25 (1970), 24–28.
M. Pilsniak, Edge motion and the distinguishing index, Theor. Comput. Sci. 678 (2017), 56–62.
M. Pilsniak, Improving upper bounds for the distinguishing index, Ars Math. Contem. 13 (2017), 259-274.
P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962), 47–52.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.