Skip to Main content Skip to Navigation
Journal articles

The generalized 3-connectivity of Lexicographic product graphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179222
Contributor : Hélène Lowinger <>
Submitted on : Wednesday, July 22, 2015 - 9:15:30 AM
Last modification on : Friday, April 12, 2019 - 2:26:48 PM
Long-term archiving on: : Friday, October 23, 2015 - 10:25:21 AM

File

dmtcs-16-1-21.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01179222, version 1

Collections

Citation

Xueliang Li, Yaping Mao. The generalized 3-connectivity of Lexicographic product graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.339--353. ⟨hal-01179222⟩

Share

Metrics

Record views

152

Files downloads

1370