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

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

2009-10-28

arxiv.org/abs/0910.5380v2

Mathematics

Combinatorics

24 pages, 8 figures

Scientific paper

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$, $SIG_\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 \geq 1$. If $\beta = 2^k - 1$, then $SIG_\infty (T) \in \{k, k+1\}$. We show that both values are possible.

Affiliated with

Also associated with

No associations

Rating

On the SIG dimension of trees under $L_{\infty}$ metric does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the SIG dimension of trees under $L_{\infty}$ metric, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the SIG dimension of trees under $L_{\infty}$ metric will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718387