Name
Abstract | ||
|---|---|---|
Let \({{\mathcal P},}\) where \({|{\mathcal P}| \geq 2,}\) be a set of points in d-dimensional space with a given metric ρ. For a point \({p \in {\mathcal P},}\) let r p be the distance of p with respect to ρ from its nearest neighbor in \({{\mathcal P}.}\) Let B(p,r p ) be the open ball with respect to ρ centered at p and having the radius r p . We define the sphere-of-influence graph (SIG) of \({{\mathcal P}}\) as the intersection graph of the family of sets \({\{B(p,r_p)\ | \ p\in {\mathcal P}\}.}\) Given a graph G, a set of points \({{\mathcal P}_G}\) in d-dimensional space with the metric ρ is called a d-dimensional SIG-representation of G, if G is isomorphic to the SIG of \({{\mathcal P}_G.}\) It is known that the absence of isolated vertices is a necessary and sufficient condition for a graph to have a SIG-representation under the L ∞-metric in some space of finite dimension. The SIG-dimension under the L ∞-metric of a graph G without isolated vertices is defined to be the minimum positive integer d such that G has a d-dimensional SIG-representation under the L ∞-metric. It is denoted by SIG ∞(G). We study the SIG-dimension of trees under the L ∞-metric and almost completely answer an open problem posed by Michael and Quint (Discrete Appl Math 127:447–460, 2003). Let T be a tree with at least two vertices. For each \({v\in V(T),}\) let leaf-degree(v) denote the number of neighbors 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) = α}. If |S| = 1, we define β(T) = α(T) − 1. Otherwise define β(T) = α(T). We show that for a tree \({T, SIG_\infty(T) = \lceil \log_2(\beta + 2)\rceil}\) where β = β (T), provided β is not of the form 2 k − 1, for some positive integer k ≥ 1. If β = 2 k − 1, then \({SIG_\infty (T) \in \{k, k+1\}.}\) We show that both values are possible. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00373-012-1160-4 | Graphs and Combinatorics |
Keywords | Field | DocType |
Sphere of influence graphs, Trees, L∞ norm, Intersection graphs | Integer,Topology,Discrete mathematics,Graph,Family of sets,Combinatorics,Vertex (geometry),Ball (mathematics),Intersection graph,Isomorphism,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 1435-5914 |
Citations | PageRank | References |
1 | 0.48 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Sunil Chandran | 1 | 552 | 54.01 |
| Rajesh Hemant Chitnis | 2 | 101 | 8.44 |
| Ramanjit Kumar | 3 | 1 | 0.82 |