(Department of Mathematics and Statistics, University of Winnipeg)

Metric Dimension of Circulant Graphs and Cayley Hypergraphs

Date: Friday, March 9, 2018

A pair of vertices $x$ and $y$ in a graph (or hypergraph) $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset of its vertices $W$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the emph{metric dimension} of $G$. The problem of determining the metric dimension of a graph is known to be NP-hard (Khuller et al 1994). The metric dimension of a graph has applications in network discovery and verification, combinatorial optimization, chemistry, and many other areas, and consequently this graph parameter has received a great deal of attention from researchers, the main goal being to determine the metric dimension of certain classes of graphs or to achieve asymptotic bounds. In particular, there is great interest in finding classes of graphs whose metric dimension does not grow with the number of vertices. Such graphs are said to have bounded metric dimension. In this talk, we bound the metric dimension of Cayley hypergraphs on finite Abelian groups with the canonical set of generators, and we show that the metric dimension of these hypergraphs is equal to the metric dimension of a Cartesian product of a circulant graphs of the form $C_n(1,2,ldots,t)=Cay(mathbb Z_n:{pm 1,pm 2,ldots,pm t})$. These circulant graphs have bounded metric dimension (Grigorious et al 2014). In fact, their metric dimension is determined by the congruence class of $n$ modulo $2t$. We present some background on the problem and some new results. We also bound the metric dimension of Cartesian products of these circulants, which yields bounds on the metric dimension of the corresponding Cayley hypergraphs. This is joint work with my students Adam Borchert and Kevin Chau.

Click for abstract

Important Dates

March 30: Good Friday (University Closed)

April 1: Easter Sunday (University Closed)