Path-connectivity of lexicographic product graphs

Abstract

Dirac showed that in a $(k-1)$-connected graph there is a path through all the k vertices. The k-path-connectivity ${\pi }_k(G)$ of a graph G, which is a generalization of Dirac's notion, was introduced by Hager in 1986. Denote by $G\circ H$ the lexicographic product of two graphs G and H. In this paper, we prove that ${\pi }_3(G\circ H)\ge {\pi }_3(G)\lfloor (|V(H)|-1)/2\rfloor +1$ for any two connected graphs G and H. Moreover, the bound is sharp. We also derive an upper bound of ${\pi }_3(G\circ H)$, that is, ${\pi }_3(G\circ H)\le 2{\pi }_3(G)|V(H)|$.

Keywords:

• connectivity
• internally disjoint paths connecting S
• packing
• path-connectivity
• lexicographic product

2010 AMS Subject Classifications:

• 05C05
• 05C40
• 05C70
• 05C76

Acknowledgments

The author is very grateful to the editor and two referees' valuable comments and suggestions, which helped to improve the presentation of this paper. Supported by the National Science Foundation of China (No. 11161037) and the Science Found of Qinghai Province (No. 2014-ZJ-907).

Disclosure statement

No potential conflict of interest was reported by the author(s).