The generalized 3-connectivity of Lexicographic product graphs
Xueliang Li, Yaping Mao
Abstract
The generalized k-connectivity
κk(G) of a graph G, first
introduced by Hager, is a natural generalization of the concept of
(vertex-)connectivity. Denote by GˆH and
G&Box;H the lexicographic product and Cartesian product
of two graphs G and H, respectively. In this
paper, we prove that for any two connected graphs G and
H, κ3(GˆH)≥
κ3(G)|V(H)|. We also give upper bounds for
κ3(G&Box; H) and
κ3(GˆH). Moreover, all the bounds
are sharp.
Full Text: PDF PostScript