Extending the metric dimension to graphs with missing edges

Sabina Zejnilović; Dieter Mitsche; João Gomes; Bruno Sinopoli

doi:10.1016/j.tcs.2015.10.022

Extending the metric dimension to graphs with missing edges

Sabina Zejnilović
, Dieter Mitsche
, João Gomes
, Bruno Sinopoli

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We define an extended metric dimension for graphs with some edges missing, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to S in all minimally connected graphs that result from completing the original graph. This extension allows for incomplete knowledge of the underlying graph in applications such as localizing the source of infection. We give precise values for the extended metric dimension when the original graph's disconnected components are trees, cycles, grids, complete graphs, and we provide general upper bounds on this number in terms of the boundary of the graph.

Original language	English
Pages (from-to)	384-394
Number of pages	11
Journal	Theoretical Computer Science
Volume	609
DOIs	https://doi.org/10.1016/j.tcs.2015.10.022
State	Published - Jan 4 2016

Keywords

Cycle graph
Graph boundary
Graph theory
Grid
Metric dimension
Tree graph

Access to Document

10.1016/j.tcs.2015.10.022

Cite this

@article{3a98df4b09a94022ac09557179ec7c1d,

title = "Extending the metric dimension to graphs with missing edges",

abstract = "The metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We define an extended metric dimension for graphs with some edges missing, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to S in all minimally connected graphs that result from completing the original graph. This extension allows for incomplete knowledge of the underlying graph in applications such as localizing the source of infection. We give precise values for the extended metric dimension when the original graph's disconnected components are trees, cycles, grids, complete graphs, and we provide general upper bounds on this number in terms of the boundary of the graph.",

keywords = "Cycle graph, Graph boundary, Graph theory, Grid, Metric dimension, Tree graph",

author = "Sabina Zejnilovi{\'c} and Dieter Mitsche and Jo{\~a}o Gomes and Bruno Sinopoli",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = jan,

day = "4",

doi = "10.1016/j.tcs.2015.10.022",

language = "English",

volume = "609",

pages = "384--394",

journal = "Theoretical Computer Science",

issn = "0304-3975",

}

TY - JOUR

T1 - Extending the metric dimension to graphs with missing edges

AU - Zejnilović, Sabina

AU - Mitsche, Dieter

AU - Gomes, João

AU - Sinopoli, Bruno

PY - 2016/1/4

Y1 - 2016/1/4

N2 - The metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We define an extended metric dimension for graphs with some edges missing, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to S in all minimally connected graphs that result from completing the original graph. This extension allows for incomplete knowledge of the underlying graph in applications such as localizing the source of infection. We give precise values for the extended metric dimension when the original graph's disconnected components are trees, cycles, grids, complete graphs, and we provide general upper bounds on this number in terms of the boundary of the graph.

AB - The metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We define an extended metric dimension for graphs with some edges missing, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to S in all minimally connected graphs that result from completing the original graph. This extension allows for incomplete knowledge of the underlying graph in applications such as localizing the source of infection. We give precise values for the extended metric dimension when the original graph's disconnected components are trees, cycles, grids, complete graphs, and we provide general upper bounds on this number in terms of the boundary of the graph.

KW - Cycle graph

KW - Graph boundary

KW - Graph theory

KW - Grid

KW - Metric dimension

KW - Tree graph

UR - https://www.scopus.com/pages/publications/84951299286

U2 - 10.1016/j.tcs.2015.10.022

DO - 10.1016/j.tcs.2015.10.022

M3 - Article

AN - SCOPUS:84951299286

SN - 0304-3975

VL - 609

SP - 384

EP - 394

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Extending the metric dimension to graphs with missing edges

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this