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 π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 ωk(G) of a graph G. Denote by G ○ H the lexicographic product of two graphs G and H. In this paper, we prove that ω3(G∘H)≥ω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 ω3(G ○ H), that is, ω3(G∘H)≤min{2ω3(G)|V(H)|2,δ(H)+δ(G)|V(H)|}. We demonstrate the usefulness of the proposed constructions by applying them to some instances of lexicographic product networks.