• Speaker: Prof Rajan Bharati, Loyola College
  • Title: Conditional Resolvability in Graphs
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 2:00 pm, Tue, 5th Nov 2013
  • Abstract:

    Let $G$ be a connected graph with vertex set $V$ and edge set $E$. The distance $d(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a shortest $u-v$ path in $G$. For an ordered set $W = \{w_1, w_2, ..., w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the code of $v$ with respect to $W$ is the $k$-vector \begin{equation} C_W(v)=(d(v,w_1),d(v,w_2), ..., d(v,w_k)). \end{equation} The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct codes with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is called a minimum resolving set or a basis for $G$. The metric dimension, denoted, $dim(G)$ is the number of vertices in a basis for $G$. The problem of finding the metric dimension of an arbitrary graph is NP-complete.

    The problem of finding minimum metric dimension is NP-complete for general graphs. Manuel et al. have proved that this problem remains NP-complete for bipartite graphs. The minimum metric dimension problem has been studied for trees, multi-dimensional grids, Petersen graphs, torus networks, Benes and butterfly networks, honeycomb networks, X-trees and enhanced hypercubes.

    These concepts have been extended in various ways and studied for different subjects in graph theory, including such diverse aspects as the partition of the vertex set, decomposition, orientation, domination, and coloring in graphs. Many invariants arising from the study of resolving sets in graph theory offer subjects for applicable research.

    The theory of conditional resolvability has evolved by imposing conditions on the resolving set. This talk is to recall the concepts and mention the work done so far and future work.

  • [Permanent link]