Resolvability in Hypergraphs

Imran Javaid, Azeem Haider, Muhammad Salman, Sadaf Mehtab

Published 2014-08-23Version 1

An ordered set $W$ of vertices of a connected graph $G$ is called a resolving set for $G$ if for every two distinct vertices $u,v \in V(G)$, there is a vertex $w \in W$ such that $d(u,w) \neq d(v,w)$. A resolving set of minimum cardinality is called a basis for $G$ and the number of vertices in a basis is called the metric dimension of $G$, denoted by $dim(G)$. For a vertex $u$ of $G$ and a subset $S$ of $V(G)$, the distance between $u$ and $S$ is the number $\min \limits_{s \in S}d(u,s)$. An ordered $t$-partition $\Pi$ $=$ $\{S_1, S_2,\ldots,S_t\}$ of $V(G)$ is called a resolving partition if for every two distinct vertices $u,v \in V(G)$, there is a set $S_i$ in $\Pi$ such that $d(u,S_i) \neq d(v,S_i)$. The minimum $t$ for which there is a resolving $t$-partition of $V(G)$ is called the partition dimension of $G$, denoted by $pd(G)$. A hypergraph is a generalization of a graph where edges can connect any number of vertices. In this paper, we extend the study of metric and partition dimension to hypergraphs. We give sharp lower bounds for the metric and partition dimension of hypergraphs in general and give exact values with specified conditions.