Edge-locating coloring of graphs
Abstract
An edge-locating coloring of a simple connected graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance to the matchings. The minimum number of the matchings of G that admits an edge-locating coloring is the edge-locating chromatic number of G, and denoted by χ′L(G). This paper introduces and studies the concept of edge-locating coloring. Graphs G with χ′L(G)∈{2, m} are characterized, where m is the size of G. We investigate the relationship between order, diameter and edge-locating chromatic number. We obtain the exact values of χ′L(Kn) and χ′L(Kn − M), where M is a maximum matching; indeed this result is also extended for any graph. We determine the edge-locating chromatic number of the join graphs of some well-known graphs. In particular, for any graph G, we show a relationship between χ′L(G + K1) and Δ(G). We investigate the edge-locating chromatic number of trees and present a characterization bound for any tree in terms of maximum degree, number of leaves, and the support vertices of trees. Finally, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.1.6
References
M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3(1) (1996), #R18.
L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Hungar. 29(1–2) (1977), 193–200.
E.T. Baskoro and Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1(2) (2013), 109–117.
A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs, Ars Combin. 126 (2016), 221–235.
J.A. Bondy and U.S.R. Murty, Graph Theory, Springer-Verlag, (2008).
D.L. Boutin, Identifying graph automorphisms using determining sets, Electron. J. Combin., 13(1) (2006), Research Paper 78 (electronic), 14 pp.
D.L. Boutin, The determining number of a Cartesian product, J. Graph Theory 61(2) (2009), 77–87.
J. Cáceres, D. Garijo, A. González, A. Márquez, and M. L. Puertas, The determining number of Kneser graphs, Discrete Math. Theor. Comput. Sci. 15(1) (2013), 1–14.
Cáceres, D. Garijo, M.L. Puertas, and C. Seara, On the determining number and the metric dimension of graphs, Electron. J. Combin. 17(1) (2010), Research Paper 63, 20 pp.
G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, Graphs of order n with locating-chromatic number n − 1, Discrete Math. 269 (2003), 65–79.
G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang. The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89-101.
K.L. Collins and A.N. Trenk, The Distinguishing Chromatic Number, Electron. J. Combin. 13 (2006).
G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman and Hall=CRC Press, Boca Raton, FL, (2009).
D. Erwin and F. Harary, Destroying automorphisms by fixing nodes, Discrete Math. 306(24) (2006), 3244–3252.
D. Garijo, A. González, and A. Márquez, The difference between the metric dimension and the determining number of a graph, Appl. Math. Comput 249 (2014), 487–501.
F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
A. Irawan, Asmiati, L. Zakaria, and K. Muludi. The locating-chromatic number of origami graphs, Algorithms 14 167, (2021).
R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015), 124-131.
R. Kalinowski, M. Pilśniak, and M. Prorok. Distinguishing arc-colourings of symmetric digraphs, Art Discrete Appl. Math. 2 (2023), #P2.04.
A. Kelenc, N. Tratnik, and I.G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math. 251 (2018), 204–220.
M. Korivand, A. Erfanian, and E.T. Baskoro, On the comparison of the distinguishing coloring and the locating coloring of graphs. Mediterr. J. Math. 20(252) (2023). D. Kuziak and I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (2021).
D.A. Mojdeh, On the conjectures of neighbor locating coloring of graphs, Theoret. Comput. Sci. 922 (2022), 300-307.
R. Nasir, S. Zafar, and Z. Zahid, Edge metric dimension of graphs, Ars Combin. 147 (2019), 143-156.
J. Pan and X. Guo, The full automorphism groups determining sets and resolving sets of coprime graphs, Graphs Combin. 35(2) (2019), 485–501.
M.H. Shekarriz, B. Ahmadi, S.A. Talebpour, and M. H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory 103 (2022), 359-377.
I.W. Sudarsana, F. Susanto, and S. Musdalifah, The locating chromatic number for m-shadow of a connected graph, Electron. J. Graph Theory Appl. 10(2) (2022), 589–601.
P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
R.C. Tillquist, R.M. Frongillo, and M.E. Lladser. Getting the lay of the land in discrete space: A survey of metric dimension and its applications. arXiv:2104.07201 [math.CO] (2021).
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.