Path-connectivity of lexicographic product graphs. Issue 1 (2nd January 2016) - Mao, Yaping
Abstract : Dirac showed that in a ( k − 1 ) -connected graph there is a path through all the k vertices. The k -path-connectivity π k ( G ) of a graph G, which is a generalization of Dirac's notion, was introduced by Hager in 1986. Denote by G ∘ H the lexicographic product of two graphs G and H . In this paper, we prove that π 3 ( G ∘ H ) ≥ π 3 ( G ) ⌊ ( | V ( H ) | − 1 ) / 2 ⌋ + 1 for any two connected graphs G and H . Moreover, the bound is sharp. We also derive an upper bound of π 3 ( G ∘ H ), that is, π 3 ( G ∘ H ) ≤ 2 π 3 ( G ) | V ( H ) | .