On the SIG dimension of trees under $L_{\infty }$ metric

Abstract

We study the $SIG$ dimension of trees under $L_{\infty }$ metric and answer an open problem posed by Michael and Quint (Discrete Applied Mathematics: 127, pages 447-460, 2003). Let $T$ be a tree with atleast two vertices. For each $v\in V(T)$, let leaf-degree$(v)$ denote the number of neighbours of $v$ that are leaves. We define the maximum leaf-degree as $\alpha (T)={\max }_{x\in V(T)}$ leaf-degree$(x)$. Let $S=\{v\in V(T)|$ leaf-degree$(v)=\alpha \}$. If $|S|=1$, we define $\beta (T)=\alpha (T)-1$. Otherwise define $\beta (T)=\alpha (T)$. We show that for a tree $T$, $SI{G}_{\infty }(T)=\lceil {\log }_2(\beta +2)\rceil$ where $\beta =\beta (T)$, provided $\beta$ is not of the form $2^k-1$, for some positive integer $k\ge 1$. If $\beta =2^k-1$, then $SI{G}_{\infty }(T)\in \{k,k+1\}$. We show that both values are possible.

24 pages, 8 figures