Optimal edge fault-tolerant embedding of a star over a cycle.

Abstract

An embedding of a guest graph G over a host graph H is an injective map Φ from the vertices of G to the vertices of H and a mapping ρ, which associates every edge e = {x, y} in G to a Φ(x)-Φ(y) path ρ(e) in H. Given an edge f in H, if ρ−1 is the set of those edges that cross f, i.e., {e : f ∈ ρ(e)}, then the cardinality of ρ−1(f) is the (edge) congestion congρ(f) of f. The length of ρ(e) is called the dilatation dil(e) of e. The sum of all the dilatations is the cost of the embedding. The removal of an edge f of H gives rise to a surviving graph Gf = G\ρ−1(f). Given positive integers n and b, and a fixed vertex v of the n-cycle Cn, we are facing the problem of finding a guest graph G of n vertices with an embedding (Φ, ρ) over Cn of minimum cost, such that for any surviving graph Gf there is an embedding of the star Sn = K1,n−1 over Gf that associates the center of the star to Φ−1(v), with congestions not greater than b. This work presents the optimal cost as well as a family of optimal solutions.