The Undirected Optical Indices of Trees

Abstract

For a connected graph $G$, an instance $I$ is a set of pairs of vertices and a corresponding routing $R$ is a set of paths specified for all vertex-pairs in $I$. Let ${\mathfrak{R}}_I$ be the collection of all routings with respect to $I$. The undirected optical index of $G$ with respect to $I$ refers to the minimum integer $k$ to guarantee the existence of a mapping $\ddot{I}•:R\to \{1,2,\dots ,k\}$, such that $\ddot{I}•(P)\ne \ddot{I}•(P^{\prime })$ if $P$ and $P^{\prime }$ have common edge(s), over all routings $R\in {\mathfrak{R}}_I$. A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let $w(G,I)$ and $\ddot{I}€(G,I)$ denote the undirected optical index and edge-forwarding index with respect to $I$, respectively. In this paper, we derive the inequality $w(T,I_A)<\frac{3}{2}\ddot{I}€(T,I_A)$ for any tree $T$, where $I_A:=\{\{x,y\}:x,y\in V(T)\}$ is the all-to-all instance.

20 pages, 4 figures