Loading…

The doubly metric dimensions of cactus graphs and block graphs

Given a connected graph G , two vertices u , v ∈ V ( G ) doubly resolve x , y ∈ V ( G ) if d G ( x , u ) - d G ( y , u ) ≠ d G ( x , v ) - d G ( y , v ) . The doubly metric dimension ψ ( G ) of G is the cardinality of a minimum set of vertices that doubly resolves each pair of vertices from V ( G )....

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2024-05, Vol.47 (4), Article 67
Main Authors: Nie, Kairui, Xu, Kexiang
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a connected graph G , two vertices u , v ∈ V ( G ) doubly resolve x , y ∈ V ( G ) if d G ( x , u ) - d G ( y , u ) ≠ d G ( x , v ) - d G ( y , v ) . The doubly metric dimension ψ ( G ) of G is the cardinality of a minimum set of vertices that doubly resolves each pair of vertices from V ( G ). It is well known that deciding the doubly metric dimension of G is NP-hard. In this work we determine the exact values of doubly metric dimensions of unicyclic graphs which completes the known result. Furthermore, we give formulae for doubly metric dimensions of cactus graphs and block graphs.
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-024-01168-0