The fractional $k$-truncated metric dimension of graphs

DOI10.1007/978-3-030-92681-6_44arXiv2108.02745MaRDI QIDQ6374606

Publication date: 5 August 2021

Abstract: The metric dimension,

d i m (G)

, and the fractional metric dimension,

d i m_{f} (G)

, of a graph

G

have been studied extensively. Let

G

be a graph with vertex set

V (G)

, and let

d (x, y)

denote the length of a shortest

x - y

path in

G

. Let

k

be a positive integer. For any

x, y i n V (G)

, let

d_{k} (x, y) = m i n d (x, y), k + 1

and let

R_{k} x, y = z i n V (G) : d_{k} (x, z) e q d_{k} (y, z)

. A set

S s u b s e t e q V (G)

is a emph{

k

-truncated resolving set} of

G

if

| S c a p R_{k} x, y | g e 1

for any distinct

x, y i n V (G)

, and the emph{

k

-truncated metric dimension}

d i m_{k} (G)

of

G

is the minimum cardinality over all

k

-truncated resolving sets of

G

. For a function

g

defined on

V (G)

and for

U s u b s e t e q V (G)

, let

g (U) = s u m_{s i n U} g (s)

. A real-valued function

g : V (G) i g h t a r r o w [0, 1]

is a emph{

k

-truncated resolving function} of

G

if

g (R_{k} x, y) g e 1

for any distinct

x, y i n V (G)

, and the emph{fractional

k

-truncated metric dimension}

d i m_{k, f} (G)

of

G

is

k

. Note that

d i m_{k, f} (G)

reduces to

d i m_{k} (G)

if the codomain of

k

-truncated resolving functions is restricted to

0, 1

, and

d i m_{k, f} (G) = d i m_{f} (G)

if

k

is at least the diameter of

G

. In this paper, we study the fractional

k

-truncated metric dimension of graphs. For any connected graph

G

of order

n g e 2

, we show that

1 l e d i m_{k, f} (G) l e f r a c n 2

; we characterize

G

satisfying

d i m_{k, f} (G)

equals

1

and

f r a c n 2

, respectively. We examine

d i m_{k, f} (G)

of some graph classes. We also show the existence of non-isomorphic graphs

G

and

H

such that

d i m_{k} (G) = d i m_{k} (H)

and

d i m_{k, f} (G) e q d i m_{k, f} (H)

, and we examine the relation among

d i m (G)

,

d i m_{f} (G)

,

d i m_{k} (G)

and

d i m_{k, f} (G)

. We conclude the paper with some open problems.

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

This page was built for publication: The fractional $k$-truncated metric dimension of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374606)