The Locating Chromatic Number for the New Operation on Generalized Petersen Graphs N_P(m,1)
DOI:
https://doi.org/10.31851/sainmatika.v21i1.14864Keywords:
locating-chromatic number, new operation, generalized Petersen graphsAbstract
The locating chromatic number is a graph invariant that quantifies the minimum number of colors required for proper vertex coloring, ensuring that any two vertices with the same color have distinct sets of neighbors. This study introduces a new operation on generalized Petersen graphs denoted by N_(P(m,1)), exploring its impact on locating chromatic numbers. Through systematic analysis, we aim to determine the specific conditions under which this operation influences the locating chromatic number and provide insights into the underlying graph-theoretical properties. The method for computing the locating chromatic number for the new operation on generalized Petersen graphs, denoted by N_(P(m,1)), entails determining the lower and upper limits. The results indicate that the locating chromatic number for the new operation on the generalized Petersen graph is 4 for m=4 and 5 for m≥5. The findings contribute to a broader understanding of graph coloring.
References
Asmiati, Irawan, A., Nuryaman, A., & Muludi, K. (2023). The locating chromatic number for certain operations of origami graphs. Mathematics and Statistics, 11(1), 101–106. https://doi.org/10.13189/ms.2023.110111
Asmiati, Wamiliana, Devriyadi, & Yulianti, L. (2017). On some petersen graphs having locating chromatic number four or five. Far East Journal of Mathematical Sciences, 102(4), 769–778. https://doi.org/10.17654/MS102040769
Baskoro, E. T., & Purwasih, I. A. (2012). The locating chromatic number for corona product of graphs. Southeast-Asian J. of Sciences, 1(February 2015), 124–134.
Behtoei, A., & Anbarloei, M. (2014). The locating chromatic number of the Join of Graphs. Bulletin of the Iranian Mathematical Society, 40(6), 1491–1504.
Behtoei, Ali, & Omoomi, B. (2011). On the locating chromatic number of Kneser graphs. Discrete Applied Mathematics, 159(18), 2214–2221. https://doi.org/10.1016/j.dam.2011.07.015
Behtoei, Ali, & Omoomi, B. (2016). On the locating chromatic number of the cartesian product of graphs. Ars Combinatoria, 126, 221–235.
Chartrand, G., Erwin, D., Henning, M. A., Slater, P. J., & Zhang, P. (2002). The locating chromatic number of a graph. Bulletin of the Institute of Combinatorics and It’s Applications, 36, 89–101.
Chartrand, G., Erwin, D., Henning, M. A., Slater, P. J., & Zhang, P. (2003). Graphs of order n with locating chromatic number n - 1. Discrete Mathematics, 269(1–3), 65–79. https://doi.org/10.1016/S0012-365X(02)00829-4
Inayah, N., Aribowo, W., & Windra Yahya, M. M. (2021). The Locating Chromatic Number of Book Graph. Journal of Mathematics, 2021, 3–5. https://doi.org/10.1155/2021/3716361
Irawan, A., Asmiati, A., Zakaria, L., & Muludi, K. (2021). The locating chromatic number of origami graphs. Algorithms, 14(6), 1–15. https://doi.org/10.3390/a14060167
Sudarsana, I. W., Susanto, F., & Musdalifah, S. (2022). The locating chromatic number for m-shadow of a connected graph. Electronic Journal of Graph Theory and Applications, 10(2), 589–601. https://doi.org/10.5614/ejgta.2022.10.2.18
Surbakti, N. M., Kartika, D., Nasution, H., & Dewi, S. (2023). The Locating Chromatic Number for Pizza Graphs. Sainmatika: Jurnal Ilmiah Matematika Dan Ilmu Pengetahuan Alam, 20(2), 126–131. https://doi.org/10.31851/sainmatika.v20i2.13085
Watkins, M. E. (1969). A theorem on tait colorings with an application to the generalized Petersen graphs. Journal of Combinatorial Theory, 6(2), 152–164. https://doi.org/10.1016/S0021-9800(69)80116-X
Welyyanti, D., Baskoro, E. T., Simajuntak, R., & Uttunggadewa, S. (2017). On the locating chromatic number for graphs with two homogenous components. Journal of Physics: Conference Series, 893(1). https://doi.org/10.1088/1742-6596/893/1/012040
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
