Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5775752 | Applied Mathematics and Computation | 2017 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yaping Mao,