The Undirected Optical Indices of Trees

Authors Yuan-Hsun Lo, Hung-Lin Fu, Yi-Jin Zhang, Wing Shing Wong

Publication date 28 August 2018

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Applications of graph theory (05C90)

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

m a t h f r a k 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

p h i : R o 1, 2, l d o t s, k

, such that

p h i (P) e q p h i (P^{'})

if

P

and

P^{'}

have common edge(s), over all routings

R i n m a t h f r a k 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

p 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}) < f r a c 32 p i (T, I_{A})

for any tree

T

, where

I_{A} := x, y :, x, y i n V (T)

is the all-to-all instance.

This page was built for publication: The Undirected Optical Indices of Trees

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