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 )....
Saved in:
Published in: | Journal of combinatorial optimization 2024-05, Vol.47 (4), Article 67 |
---|---|
Main Authors: | , |
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!
|
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 |