Path-connectivity of lexicographic product graphs. Issue 1 (2nd January 2016)

• Record Type: Journal Article
• Authors: Mao, Yaping
• Is Part Of: International journal of computer mathematics. Volume 93:Issue 1(2016)
• Page Start: 27
• Page End: 39
• Publication Date: 2016-01-02
• Subjects: connectivity -- internally disjoint paths connecting S -- packing -- path-connectivity -- lexicographic product; 05C05 -- 05C40 -- 05C70 -- 05C76; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2014.987762
• Languages: English
• ISSNs: 0020-7160

Abstract

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 ) | .