Constructing edge-disjoint Steiner paths in lexicographic product networks

Yaping Mao

Applied Mathematics and Computation, 2017, vol. 308, issue C, 1-10

Abstract: 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.

Keywords: Edge-connectivity; Steiner tree; Edge-disjoint Steiner paths; Packing; Path edge-connectivity; Lexicographic product (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317301893
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:308:y:2017:i:c:p:1-10

DOI: 10.1016/j.amc.2017.03.015

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().