On the Edge Decomposition of the Complete Multipartite Graph and Certain Generalized Petersen Graphs into Locally Irregular Subgraphs
DOI:
https://doi.org/10.11113/mjfas.v21n6.4250Keywords:
Locally irregular, subcubic graph, complete multipartite graph, generalized Petersen graphAbstract
The least number of colors to decompose a graph into a locally irregular edge coloring is the locally irregular chromatic index and is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>χ</mi><mo>'</mo><mstyle mathvariant="normal"><mtext>irr</mtext></mstyle><mo>(</mo><mi>G</mi><mo>)</mo></math>. In 2015, Baudon et al. showed that, for the complete bipartite graph <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>K</mi><mi>m,n</mi></msub></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>χ</mi><mo>'</mo><mstyle mathvariant="normal"><mtext>irr</mtext></mstyle><mo>(</mo><msub><mi>K</mi><mi>m,n</mi></msub><mo>)</mo><mo>=</mo><mn>3</mn></math>.
In this paper, we determine the locally irregular chromatic index for complete multipartite graphs. In 2023, B. Lužar et al. conjectured that, for generalized Petersen graphs <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo>)</mo></math> with girth at least 5 (except <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mn>5</mn><mo>,</mo><mn>2</mn><mo>)</mo></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mn>7</mn><mo>,</mo><mn>2</mn><mo>)</mo></math>), <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>χ</mi><mo>'</mo><mstyle mathvariant="normal"><mtext>irr</mtext></mstyle><mo>(</mo><mi>GP</mi><mo>(</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo>)</mo><mo>)</mo><mo>=</mo><mn>3</mn></math>.
Here, we partially verify the conjecture for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mi>n</mi><mo>,</mo><mn>2</mn><mo>)</mo></math> and determine the exact values for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mn>5</mn><mo>,</mo><mn>2</mn><mo>)</mo></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mn>7</mn><mo>,</mo><mn>2</mn><mo>)</mo></math>, and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>GP</mi><mo>(</mo><mn>9</mn><mo>,</mo><mn>2</mn><mo>)</mo></math>. The exact values of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>χ</mi><mo>'</mo><mstyle mathvariant="normal"><mtext>irr</mtext></mstyle><mo>(</mo><mi>GP</mi><mo>(</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo>)</mo><mo>)</mo></math> are also determined for cases when <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi></math> satisfy certain conditions.
References
Sullivan, B. D., Weerapurage, D., & Groer, C. (2013). Parallel algorithms for graph optimization using tree decompositions. In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and PhD Forum (pp. 1838–1847). IEEE. https://doi.org/10.1109/IPDPSW.2013.242.
Yow, K. S., & Li, C. (2024, November). D&A: Resource optimization in personalized PageRank computations using multi-core machines. IEEE Transactions on Knowledge and Data Engineering, 36(11), 5905–5910. https://doi.org/10.1109/TKDE.2024.3417264
Ghane-Ezabadi, M., & Vergara, H. A. (2016, May). Decomposition approach for integrated intermodal logistics network design. Transportation Research Part E: Logistics and Transportation Review, 89, 53–69. https://doi.org/10.1016/j.tre.2016.02.009.
CGroer, C. S., Sullivan, B. D., & Weerapurage, D. P. (2012, October). INDDGO: Integrated Network Decomposition & Dynamic programming for graph optimization. Oak Ridge, TN: Oak Ridge National Laboratory. https://doi.org/10.2172/1055043.
Soranzo, N., Ramezani, F., Iacono, G., Altafini, C., & Bioinformatica, C. (2010). Graph-theoretical decompositions of large-scale biological networks. Automatica, 1–17.
Xu, Y., Xu, D., & Gabow, H. N. (2000, December). Protein domain decomposition using a graph-theoretic approach. Bioinformatics, 16(12), 1091–1104. https://doi.org/10.1093/bioinformatics/16.12.1091.
Levinkov, E., et al. (2017, July). Joint graph decomposition & node labeling: Problem, algorithms, applications. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
Malliaros, F. D., Giatsidis, C., Papadopoulos, A. N., & Vazirgiannis, M. (2020, January). The core decomposition of networks: Theory, algorithms and applications. The VLDB Journal, 29(1), 61–92. https://doi.org/10.1007/s00778-019-00587-4.
Baudon, O., Bensmail, J., & Sopena, É. (2015, January). On the complexity of determining the irregular chromatic index of a graph. Journal of Discrete Algorithms, 30, 113–127. https://doi.org/10.1016/j.jda.2014.12.008,
Avazbeigi, M. (2009). An overview of complexity theory (pp. 19–36). https://doi.org/10.1007/978-3-7908-2151-2_2.
Karp, R. M. (2010). Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958–2008 (pp. 219–241). Springer. https://doi.org/10.1007/978-3-540-68279-0_8.
Gomes, C. P., Kautz, H., Sabharwal, A., & Selman, B. (2008). Satisfiability solvers. In Handbook of Satisfiability (pp. 89–134). https://doi.org/10.1016/S1574-6526(07)03002-7.
Baudon, O., Bensmail, J., Przybyło, J., & Woźniak, M. (2015). On decomposing regular graphs into locally irregular subgraphs. European Journal of Combinatorics, 49, 90–104. https://doi.org/10.1016/j.ejc.2015.02.031
Bensmail, J., Dross, F., & Nisse, N. (2020). Decomposing degenerate graphs into locally irregular subgraphs. Graphs and Combinatorics, 36(6), 1869–1889. https://doi.org/10.1007/s00373-020-02193-6.
Bensmail, J., Merker, M., & Thomassen, C. (2017). Decomposing graphs into a constant number of locally irregular subgraphs. European Journal of Combinatorics, 60, 124–134. https://doi.org/10.1016/j.ejc.2016.09.011.
Lužar, B., Przybyło, J., & Soták, R. (2018). New bounds for locally irregular chromatic index of bipartite and subcubic graphs. Journal of Combinatorial Optimization, 36(4), 1425–1438. https://doi.org/10.1007/s10878-018-0313-7.
Sedlar, J., & Škrekovski, R. (2021). Remarks on the local irregularity conjecture. Mathematics, 9(24), 3209. https://doi.org/10.3390/math9243209.
Lei, H., Lian, X., Shi, Y., & Zhao, R. (2022). Graph classes with locally irregular chromatic index at most 4. Journal of Optimization Theory and Applications, 195(3), 903–918. https://doi.org/10.1007/s10957-022-02119-7.
Sedlar, J., & Škrekovski, R. (2024). Local irregularity conjecture vs. cacti. Discrete Applied Mathematics, 343, 115–133. https://doi.org/10.1016/j.dam.2023.10.005.
Lužar, B., Maceková, M., Rindošová, S., Soták, R., Sroková, K., & Štorgel, K. (2023). Locally irregular edge-coloring of subcubic graphs. Discrete Applied Mathematics, 339, 136–148. https://doi.org/10.1016/j.dam.2023.06.020
Grzelec, I., Madaras, T., Onderko, A., & Soták, R. (2024). On a new problem about the local irregularity of graphs.
Steimle, A., & Staton, W. (2009). The isomorphism classes of the generalized Petersen graphs. Discrete Mathematics, 309(1), 231–237. https://doi.org/10.1016/j.disc.2007.12.074.
Sim, K. A., Tan, T. S., & Wong, K. B. (2018). On the burning number of generalized Petersen graphs. Bulletin of the Malaysian Mathematical Sciences Society, 41(3), 1657–1670. https://doi.org/10.1007/s40840-017-0585-6.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Kai An Sim, Jiin Yih Tan, Kok Bin Wong, Chee Kit Ho
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
