A1 Refereed original research article in a scientific journal
Complexity and Equivalency of Multiset Dimension and ID-colorings
Authors: Hakanen, Anni; Yero, Ismael G.
Publisher: IOS PRESS
Publishing place: AMSTERDAM
Publication year: 2024
Journal: Fundamenta Informaticae
Journal acronym: FUND INFORM
Volume: 191
Issue: 3-4
First page : 315
Last page: 330
Number of pages: 16
ISSN: 0169-2968
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-242185
Web address : https://content.iospress.com/articles/fundamenta-informaticae/fi242185
Preprint address: https://arxiv.org/pdf/2303.06986
Abstract
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.
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.
UTU Research Portal