Constructing edge-disjoint Steiner paths in lexicographic product networks

Dirac showed that in a (k - 1)-connected graph there is a path through each k vertices. The path k-connectivity pi(k) (G) of a graph G, which is a generalization of Dirac's notion, was introduced by Hager in 1986. It is natural to introduce the concept of path k-edge-connectivity. omega(k)(G) of a graph G. Denote by G circle H the lexicographic product of two graphs G and H. In this paper, we prove that. omega(3) (G circle H) >= omega(3)(G)[3|V(H)|/4 for any two graphs G and H. Moreover, the bound is sharp. We also derive an upper bound of omega(3)(G circle H), that is, omega(3)(G circle H) <= min{2 omega(3)(G)|V(H)|(2),delta(H) + delta(G) |V(H)|}. We demonstrate the usefulness of the proposed constructions by applying them to some instances of lexicographic product networks. (C) 2017 Elsevier Inc. All rights reserved.