On the SIG-dimension of trees under the L_-metric

DOI10.1007/S00373-012-1160-4zbMATH Open1268.05136arXiv0910.5380OpenAlexW2079653718MaRDI QIDQ354411FDOQ354411

Authors: L. Sunil Chandran, Rajesh Chitnis, Ramanjit Kumar 

Publication date: 19 July 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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 $vinV(T)$, let leaf-degree$(v)$ denote the number of neighbours of $v$ that are leaves. We define the maximum leaf-degree as $alpha(T)=ma{x}_{xinV(T)}$ leaf-degree$(x)$. Let $$ leaf-degree$$. If $|S|=1$, we define $$. Otherwise define $$. We show that for a tree $T$, $$ where $$, provided $$ is not of the form $2^k-1$, for some positive integer $kgeq1$. If $$, then $SI{G}_{i}nfty(T)ink,k+1$. We show that both values are possible.

Full work available at URL: https://arxiv.org/abs/0910.5380

Recommendations

• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Abstract sphere-of-influence graphs
• Publication:4489176
• Trees that are sphere-of-influence graphs
• Sphere-of-influence graphs using the sup-norm

zbMATH Keywords

treesintersection graphs\(L_\infty\) normsphere of influence graphs

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Abstract sphere-of-influence graphs
• Sphere of influence graphs in general metric spaces
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Trees that are sphere-of-influence graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sphere-of-influence graphs using the sup-norm

Cited In (2)

• Spherical recurrence and locally isometric embeddings of trees into positive density subsets of ℤ^d
• SIG-dimension conjecture proved for graphs having a perfect matching

This page was built for publication: On the \(SIG\)-dimension of trees under the \(L_\infty\)-metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354411)