Abstract | ||
---|---|---|
Dirac showed that in a (k−1)-connected graph there is a path through all the k vertices. The path k-connectivity πk(G) of a graph G, which is a generalization of Dirac’s notion, was introduced by Hager in 1986. As a natural counterpart of path k-connectivity, the concept of path k-edge-connectivity ωk(G) of a graph G was introduced. Denote by H∘G the lexicographic product of two graphs H and G. In this paper, for a 2-connected graph G and a graph H, we show π3(G∘H)≥|V(H)| and ω3(G∘H)≥3⌊|V(H)|∕2⌋+r, where r=|V(H)|(mod2). Moreover, the bound is sharp. In addition, the upper bounds for path 3-(edge-)connectivity of the lexicographic product of a connected graph and some specific graphs are obtained. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.dam.2019.11.014 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Connectivity,S-Steiner paths,Path 3-connectivity,Path 3-edge-connectivity,Lexicographic product | Journal | 282 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tianlong Ma | 1 | 17 | 5.69 |
Jinling Wang | 2 | 29 | 6.52 |
Mingzu Zhang | 3 | 6 | 1.10 |
Xiaodong Liang | 4 | 0 | 0.68 |