Constructing edge-disjoint Steiner trees in Cartesian product networks

Abstract

Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. For a graph $F=(V,E)$ and a set $S\subseteq V(F)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a subgraph $T=(V^{\prime },E^{\prime })$ of $F$ that is a tree with $S\subseteq V^{\prime }$. For $S\subseteq V(F)$ and $|S|\ge 2$, the {\it generalized local edge-connectivity} $\hat{I}»(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $F$. For an integer $k$ with $2\le k\le n$, the {\it generalized $k$-edge-connectivity} $\hat{I}{»}_k(F)$ of a graph $F$ is defined as $\hat{I}{»}_k(F)=\min \{\hat{I}»(S)|S\subseteq V(F)and|S|=k\}$.In this paper, we give sharp upper and lower bounds for $\hat{I}{»}_k(G\square H)$, where $\square$ is the Cartesian product operation, and $G,H$ are two graphs.

14 pages; 3 figures