Metric Dimension and Diameter in Bipartite Graphs

Peter Dankelmann; Jane Morgan; Emily Rivett-Carnac

doi:10.7151/dmgt.2382

Metric Dimension and Diameter in Bipartite Graphs

Peter Dankelmann, Jane Morgan, Emily Rivett-Carnac

Mathematics and Applied Mathematics

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

1 Citation (Scopus)

Abstract

Let G be a connected graph and W a set of vertices of G. If every vertex of G is determined by its distances to the vertices in W, then W is said to be a resolving set. The cardinality of a minimum resolving set is called the metric dimension of G. In this paper we determine the maximum number of vertices in a bipartite graph of given metric dimension and diameter. We also determine the minimum metric dimension of a bipartite graph of given maximum degree.

Original language	English
Journal	Discussiones Mathematicae - Graph Theory
DOIs	https://doi.org/10.7151/dmgt.2382
Publication status	Accepted/In press - 2021

Keywords

bipartite graph
diameter
maximum degree
metric dimension
resolving set

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.7151/dmgt.2382

Cite this

@article{4dd715c0d23742a5afbdc6f8a7ad7214,

title = "Metric Dimension and Diameter in Bipartite Graphs",

abstract = "Let G be a connected graph and W a set of vertices of G. If every vertex of G is determined by its distances to the vertices in W, then W is said to be a resolving set. The cardinality of a minimum resolving set is called the metric dimension of G. In this paper we determine the maximum number of vertices in a bipartite graph of given metric dimension and diameter. We also determine the minimum metric dimension of a bipartite graph of given maximum degree.",

keywords = "bipartite graph, diameter, maximum degree, metric dimension, resolving set",

author = "Peter Dankelmann and Jane Morgan and Emily Rivett-Carnac",

note = "Publisher Copyright: {\textcopyright} 2020 Peter Dankelmann et al., published by Sciendo.",

year = "2021",

doi = "10.7151/dmgt.2382",

language = "English",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

}

TY - JOUR

T1 - Metric Dimension and Diameter in Bipartite Graphs

AU - Dankelmann, Peter

AU - Morgan, Jane

AU - Rivett-Carnac, Emily

PY - 2021

Y1 - 2021

N2 - Let G be a connected graph and W a set of vertices of G. If every vertex of G is determined by its distances to the vertices in W, then W is said to be a resolving set. The cardinality of a minimum resolving set is called the metric dimension of G. In this paper we determine the maximum number of vertices in a bipartite graph of given metric dimension and diameter. We also determine the minimum metric dimension of a bipartite graph of given maximum degree.

AB - Let G be a connected graph and W a set of vertices of G. If every vertex of G is determined by its distances to the vertices in W, then W is said to be a resolving set. The cardinality of a minimum resolving set is called the metric dimension of G. In this paper we determine the maximum number of vertices in a bipartite graph of given metric dimension and diameter. We also determine the minimum metric dimension of a bipartite graph of given maximum degree.

KW - bipartite graph

KW - diameter

KW - maximum degree

KW - metric dimension

KW - resolving set

UR - http://www.scopus.com/inward/record.url?scp=85100802813&partnerID=8YFLogxK

U2 - 10.7151/dmgt.2382

DO - 10.7151/dmgt.2382

M3 - Article

AN - SCOPUS:85100802813

SN - 1234-3099

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

ER -

Metric Dimension and Diameter in Bipartite Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this