Anni Hakanen ; Ismael G. Yero - Complexity and equivalency of multiset dimension and ID-colorings

fi:11068 - Fundamenta Informaticae, November 10, 2024, Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday
Complexity and equivalency of multiset dimension and ID-coloringsArticle

Authors: Anni Hakanen ; Ismael G. Yero

    This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being a complete graph, and whose multiset dimension is not infinite.


    Volume: Volume 191, Issues 3-4: Iiro Honkala's 60 Birthday
    Published on: November 10, 2024
    Accepted on: November 16, 2023
    Submitted on: March 14, 2023
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05C12, 05C76

    Consultation statistics

    This page has been seen 12 times.
    This article's PDF has been downloaded 12 times.