### AIMS Mathematics

2021, Issue 6: 5762-5771. doi: 10.3934/math.2021340
Research article

# The k-subconnectedness of planar graphs

• Received: 13 November 2020 Accepted: 01 March 2021 Published: 26 March 2021
• MSC : 05C40, 05C85

• 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

### Related Papers:

• 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.
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

2.2 3