IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Bounding the Metric Dimension of a Graph

  • Nov. 16, 2018
  • 2:30 p.m.
  • LeConte 317R

Abstract

Given simple connected graph $G$ and $W=\{w _ 1,w _ 2,\ldots, w _ k\}$ is an ordered subset of $V(G)$. A representation of $v$ with respect to $W$ is the vector $r(v \vert W)=(d(v,w _ 1),d(v,w _ 2),\ldots,d(v,w _ k))$. $W$ is called a resolving set for $G$ if every two vertices of $G$ have distinct representatives. It is called a local resolving set for $G$ if every two adjacent vertices of $G$ have distinct representatives. It is called an m-resolving set for $G$ if every two vertices of $G$ have distinct representatives when we disregard its ordering and see it as a multiset. Resolving set, local resolving set, and m-resolving set with minimum number of vertices is called a basis, local basis, and multiset basis, respectively, for $G$. The cardinality of the basis, local basis, and multiset basis is called metric dimension ($\dim(G))$, local metric dimension ($lmd(G)$), and multiset metric dimension ($md(G)$), respectively. In this talk we'll see several known results of the bounds of $\dim(G)$ and its relation to $lmd(G)$, as well as the new results and open problems posted by the author that includes $md(G)$.

This is one of the invited talk at the most recent MCCCC, and is the work of Simanjuntak et al. of the Combinatorial Mathematics Research Group, that is partially supported by Indonesian Higher Education Technology Research Funds (RISTEKDIKTI PDUPT).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC