A graph $ G $ with at least $ 2k $ vertices is called k-subconnected if, for any $ 2k $ vertices $ x_{1}, x_{2}, \cdots, x_{2k} $ in $ G $, there are $ k $ independent paths joining the $ 2k $ vertices in pairs in $ G $. In this paper, we prove that a k-connected planar graph with at least $ 2k $ vertices is k-subconnected for $ k = 1, 2 $; a 4-connected planar graph is k-subconnected for each $ k $ such that $ 1\leq k\leq \nu /2 $, where $ v $ is the number of vertices of $ G $; and a 3-connected planar graph $ G $ with at least $ 2k $ vertices is k-subconnected for $ k = 4, 5, 6 $. The bounds of k-subconnectedness are sharp.
Citation: Zongrong Qin, Dingjun Lou. The k-subconnectedness of planar graphs[J]. AIMS Mathematics, 2021, 6(6): 5762-5771. doi: 10.3934/math.2021340
A graph $ G $ with at least $ 2k $ vertices is called k-subconnected if, for any $ 2k $ vertices $ x_{1}, x_{2}, \cdots, x_{2k} $ in $ G $, there are $ k $ independent paths joining the $ 2k $ vertices in pairs in $ G $. In this paper, we prove that a k-connected planar graph with at least $ 2k $ vertices is k-subconnected for $ k = 1, 2 $; a 4-connected planar graph is k-subconnected for each $ k $ such that $ 1\leq k\leq \nu /2 $, where $ v $ is the number of vertices of $ G $; and a 3-connected planar graph $ G $ with at least $ 2k $ vertices is k-subconnected for $ k = 4, 5, 6 $. The bounds of k-subconnectedness are sharp.
| [1] | O. R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congressus Numerantium, 116 (1996), 231–252. |
| [2] |
B. Peroche, On several sorts of connectivity, Discrete Math., 46 (1983), 267–277. doi: 10.1016/0012-365X(83)90121-8
|
| [3] | Z. Dvořák, J. Kára, D. Král, O. Pangrác, An algorithm for cyclic edge connectivity of cubic graphs, In: Algorithm Theory-SWAT 2004, Springer, Berlin, Heidelberg, 2004,236–247. |
| [4] | D. Lou, W. Wang, An efficient algorithm for cyclic edge connectivity of regular graphs, Ars Combinatoria, 77 (2005), 311–318. |
| [5] | D. Lou, K. Liang, An improved algorithm for cyclic edge connectivity of regular graphs, Ars Combinatoria, 115 (2014), 315–333. |
| [6] | D. Lou, A square time algorithm for cyclic edge connectivity of planar graphs, Ars Combinatoria, 133 (2017), 69–92. |
| [7] |
J. Liang, D. Lou, Z. Zhang, A polynomial time algorithm for cyclic vertex connectivity of cubic graphs, Int. J. Comput. Math., 94 (2017), 1501–1514. doi: 10.1080/00207160.2016.1210792
|
| [8] |
J. Liang, D. Lou, A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k, J. Comb. Optim., 37 (2019), 1000–1010. doi: 10.1007/s10878-018-0332-4
|
| [9] | C. Thomassen, 2-linked graphs, Eur. J. Combin., 1 (1980), 371–378. |
| [10] | B. Bollobás, A. Thomason, Highly linked graphs, Combinatorica, 16 (1996), 313–320. |
| [11] |
K. Kawarabayashi, A. Kostochka, G. Yu, On sufficient degree conditions for a graph to be k-linked, Comb. Probab. Comput., 15 (2006), 685–694. doi: 10.1017/S0963548305007479
|
| [12] |
Z. Qin, D. Lou, H. Zhu, J. Liang, Characterization of k-subconnected graphs, Appl. Math. Comput., 364 (2020), 124620. doi: 10.1016/j.amc.2019.124620
|
| [13] | J. A. Bondy, U. S. R. Murty, Graph theory with applications, MacMillan Press Ltd., 1976. |
| [14] | W. T. Tutte, A theorem on planar graphs, T. Am. Math. Soc., 82 (1956), 99–116. |
Zongrong Qin, Dingjun Lou. The k-subconnectedness of planar graphs[J]. AIMS Mathematics, 2021, 6(6): 5762-5771. doi: 10.3934/math.2021340
DownLoad: