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.
  • Reader Comments
  • © 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1877) PDF downloads(85) Cited by(1)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog