Search Advanced

AIMS Mathematics

2022, Volume 7, Issue 9: 16775-16786. doi: 10.3934/math.2022921
Previous Article Next Article
Research article

Generalized (edge-)connectivity of join, corona and cluster graphs

  • 1.
    College of Arts and Sciences, Shanghai Maritime University, Shanghai 201306, China
  • 2.
    Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, China
  • 3.
    College of Science, China Jiliang University, Hangzhou, Zhejiang 310018, China
  • 4.
    Academy of Plateau Science and Sustainability, Qinghai Normal University, Xining, Qinghai 810008, China
  • *In Summer 2020, this paper was accepted for publication in "Ars Combinatoria". As of Dec 15, 2021, the editorial board and managing editors of this journal have resigned. So we contacted the publisher and withdrawn the paper from "Ars Combinatoria" and re-submitted here.
  • Received: 25 April 2022 Revised: 26 June 2022 Accepted: 07 July 2022 Published: 13 July 2022

  • MSC : 05C40, 05C05, 05C76

  • The generalized $ k $-connectivity $ \kappa_k(G) $ of a graph $ G $, introduced by Hager in 1985, is a natural generalization of the classical connectivity. As a natural counterpart, Li et al. proposed the concept of generalized $ k $-edge-connectivity $ \lambda_k(G) $. In this paper, we obtain exact values or sharp upper and lower bounds of $ \kappa_k(G) $ and $ \lambda_k(G) $ for join, corona and cluster graphs.

    Citation: Meiqin Wei, He Zhang, Zhao Wang, Yaping Mao. Generalized (edge-)connectivity of join, corona and cluster graphs[J]. AIMS Mathematics, 2022, 7(9): 16775-16786. doi: 10.3934/math.2022921

    Related Papers:

  • The generalized $ k $-connectivity $ \kappa_k(G) $ of a graph $ G $, introduced by Hager in 1985, is a natural generalization of the classical connectivity. As a natural counterpart, Li et al. proposed the concept of generalized $ k $-edge-connectivity $ \lambda_k(G) $. In this paper, we obtain exact values or sharp upper and lower bounds of $ \kappa_k(G) $ and $ \lambda_k(G) $ for join, corona and cluster graphs.


    加载中


    [1] F. Bao, Y. Igarashi, S. R. Öhring, Reliable broadcasting in product networks, Discrete Appl. Math., 83 (1998), 3–20. https://doi.org/10.1016/S0166-218X(97)00100-5 doi: 10.1016/S0166-218X(97)00100-5
    [2] L. W. Beineke, R. J. Wilson, Topics in structural graph theory, Cambrige University Press, 2013.
    [3] J. A. Bondy, U. S. R. Murty, Graph theory, GTM 244, Springer, 2008.
    [4] G. Chartrand, S. F. Kappor, L. Lesniak, D. R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq., 2 (1984), 1–6.
    [5] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks, 55 (2010), 360–367. https://doi.org/10.1002/net.20339 doi: 10.1002/net.20339
    [6] X. Cheng, D. Du, Steiner trees in industry, Kluwer Academic Publisher, Dordrecht, 2001.
    [7] E. Cheng, L. Lipák, K. Qiu, Z. Shen, Cyclic vertex-connectivity of Cayley graphs generated by transposition trees, Graph. Combinator., 29 (2013), 835–841. https://doi.org/10.1007/s00373-012-1172-0 doi: 10.1007/s00373-012-1172-0
    [8] E. Cheng, L. Lipák, W. Yang, Z. Zhang, X. Guo, A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees, Inform. Sciences, 181 (2011), 4300–4308. https://doi.org/10.1016/j.ins.2011.05.010 doi: 10.1016/j.ins.2011.05.010
    [9] E. Cheng, K. Qiu, Z. Shen, A strong connectivity property of the generalized exchanged hypercube, Discrete Appl. Math., 216 (2017), 529–536. https://doi.org/10.1016/j.dam.2015.11.014 doi: 10.1016/j.dam.2015.11.014
    [10] D. Du, X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
    [11] K. Day, A. E. Al-Ayyoub, The cross product of interconnection networks, IEEE T. Parall. Distr., 8 (1997), 109–118. https://doi.org/10.1109/71.577251 doi: 10.1109/71.577251
    [12] D. P. Day, O. R. Oellermann, H. C. Swart, The $\ell$-connectivity function of trees and complete multipartite graphs, J. Comb. Math. Comb. Comput., 10 (1991), 183–192.
    [13] M. Feng, M. Xu, K. Wang, Identifying codes of lexicographic product of graphs, Electron. J. Combin., 19 (2012), 56–63. https://doi.org/10.37236/2974 doi: 10.37236/2974
    [14] P. Fragopoulou, S. G. Akl, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Trans. Comput., 45 (1996), 174–185. https://doi.org/10.1109/12.485370 doi: 10.1109/12.485370
    [15] M. Grötschel, The Steiner tree packing problem in VLSI design, Math. Program., 78 (1997), 265–281. https://doi.org/10.1007/BF02614374 doi: 10.1007/BF02614374
    [16] M. Grötschel, A. Martin, R. Weismantel, Packing Steiner trees: A cutting plane algorithm and commputational results, Math. Program., 72 (1996), 125–145. https://doi.org/10.1007/BF02592086 doi: 10.1007/BF02592086
    [17] M. Hager, Pendant tree-connectivity, J. Comb. Theory, 38 (1985), 179–189. https://doi.org/10.1016/0095-8956(85)90083-8 doi: 10.1016/0095-8956(85)90083-8
    [18] M. Hager, Path-connectivity in graphs, Discrete Math., 59 (1986), 53–59. https://doi.org/10.1016/0012-365X(86)90068-3 doi: 10.1016/0012-365X(86)90068-3
    [19] R. Hammack, W. Imrich, S. Klav$\breve {\rm{s}}$r, Handbook of product graphs, 2 Ed., CRC Press, 2011.
    [20] S. He, R. Hao, E. Cheng, Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theor. Comput. Sci., 731 (2018), 50–67. https://doi.org/10.1016/j.tcs.2018.04.001 doi: 10.1016/j.tcs.2018.04.001
    [21] H. R. Hind, O. R. Oellermann, Menger-type results for three or more vertices, Congr. Numer., 113 (1996), 179–204.
    [22] A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput., 79 (1988), 43–59. https://doi.org/10.1016/0890-5401(88)90016-8 doi: 10.1016/0890-5401(88)90016-8
    [23] S. Ku, B. Wang, T. Hung, Constructing edge- disjoint spanning trees in product networks, IEEE T. Parall. Distr., 14 (2003), 213–221.
    [24] W. Mader, Über die Maximalzahl kantendisjunkter A-Wege, Arch. Math., 30 (1978), 325–336.
    [25] W. Mader, Über die Maximalzahl kreuzungsfreier H-Wege, Arch. Math., 31 (1978), 387–402.
    [26] H. Li, Y. Ma, W. Yang, Y. Wang, The generalized $3$-connectivity of graph products, Appl. Math. Comput., 295 (2017), 77–83. https://doi.org/10.1016/j.amc.2016.10.002 doi: 10.1016/j.amc.2016.10.002
    [27] S. Li, J. Tu, C. Yu, The generalized $3$-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., 274 (2016), 41–46. https://doi.org/10.1016/j.amc.2015.11.016 doi: 10.1016/j.amc.2015.11.016
    [28] X. Li, Y. Mao, Generalized connectivity of graphs, Springer Briefs in Mathematics, Springer, Switzerland, 2016.
    [29] X. Li, Y. Mao, Y. Sun, On the generalized (edge-)connectivity of graphs, Australas. J. Comb., 58 (2014), 304–319. https://doi.org/10.7151/dmgt.1907 doi: 10.7151/dmgt.1907
    [30] C. S. J. A. Nash-Williams, Edge-disjonint spanning trees of finite graphs, J. London Math. Soc., 36 (1961), 445–450.
    [31] O. R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congr. Numer., 116 (1996), 231–252.
    [32] O. R. Oellermann, On the $\ell$-connectivity of a graph, Graph. Combinator., 3 (1987), 285–299.
    [33] O. R. Oellermann, A note on the $\ell$-connectivity function of a graph, Congr. Numer., 60 (1987), 181–188.
    [34] F. Okamoto, P. Zhang, The tree connectivity of regular complete bipartite graphs, J. Comb. Math. Comb. Comput., 74 (2010), 279–293.
    [35] K. Ozeki, T. Yamashita, Spanning trees: A survey, Graph. Combinator., 27 (2011), 1–26. https://doi.org/10.1007/s00373-010-0973-2 doi: 10.1007/s00373-010-0973-2
    [36] E. Palmer, On the spanning tree packing number of a graph: A survey, Discrete Math., 230 (2001), 13–21. https://doi.org/10.1016/S0012-365X(00)00066-2 doi: 10.1016/S0012-365X(00)00066-2
    [37] G. Sabidussi, Graphs with given group and given graph theoretical properties, Can. J. Math., 9 (1957), 515–525. https://doi.org/10.4153/CJM-1957-060-7 doi: 10.4153/CJM-1957-060-7
    [38] N. A. Sherwani, Algorithms for $VLSI$ physical design automation, 3Ed., Kluwer Acad. Pub., London, 1999.
    [39] S. $\breve {\rm{S}}$pacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett., 21 (2008), 682–685.
    [40] D. West, Introduction to graph theory, 2Ed., Prentice Hall, 2001.
    [41] C. Yang, J. Xu, Connectivity of lexicographic product and direct product of graphs, Ars Combinatoria, 111 (2013), 3–12.
    [42] Y. Yeh, I. Gutman, On the sum of all distances in composite graphs, Discrete Math., 135 (1994), 359–365. https://doi.org/10.1016/0012-365X(93)E0092-I doi: 10.1016/0012-365X(93)E0092-I
    [43] S. Zhao, R. Hao, E. Cheng, Two kinds of generalized connectivity of dual cubes, Discrete Appl. Math., 257 (2019), 306–316. https://doi.org/10.1016/j.dam.2018.09.025 doi: 10.1016/j.dam.2018.09.025
  • Reader Comments
  • © 2022 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搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(1247) PDF downloads(64) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog