Edge-connectivity and (signless) Laplacian eigenvalue of graphs

被引:13
|
作者
Liu, Huiqing [1 ]
Lu, Mei [2 ]
Tian, Feng [3 ]
机构
[1] Hubei Univ, Sch Math & Comp Sci, Wuhan 430062, Peoples R China
[2] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China
[3] Chinese Acad Sci, Acad Math & Syst Sdiences, Inst Syst Sci, Beijing 100080, Peoples R China
关键词
Edge-connectivity; Laplacian eigenvalue; Signless; Girth; SPECTRUM; NUMBERS; BOUNDS;
D O I
10.1016/j.laa.2013.10.017
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we first show that if the second smallest Laplacian eigenvalue of a graph is no less than (k-1)n/(delta+1)(n-1-delta) or the second largest signless Laplacian eigenvalue of a graph is no more than 2 delta - (k-1)n/(delta+1)(n-1-delta) then the graph is k-edge-connected, where is the minimum degree of the graph and n is the order of the graph. Also, we give a Laplacian eigenvalue condition and a signless Laplacian eigenvalue condition for a graph to be k-edge-connected involving the girth g of the graph, respectively. Our results generalize some known results. (C) 2013 Elsevier Inc. All rights reserved.
引用
收藏
页码:3777 / 3784
页数:8
相关论文
共 50 条
  • [31] Edge-connectivity in Pk-path graphs
    Balbuena, C
    García-Vázquez, P
    DISCRETE MATHEMATICS, 2004, 286 (03) : 213 - 218
  • [32] The restricted edge-connectivity of Kautz undirected graphs
    Fan, Ying-Mei
    Xu, Jun-Ming
    Lu, Min
    ARS COMBINATORIA, 2006, 81 : 369 - 379
  • [33] Note on fair game edge-connectivity of graphs
    Furuya, Michitaka
    Matsumoto, Naoki
    Ohno, Yumiko
    Ozeki, Kenta
    DISCRETE APPLIED MATHEMATICS, 2023, 333 : 132 - 135
  • [34] On size, order, diameter and edge-connectivity of graphs
    P. Ali
    J. P. Mazorodze
    S. Mukwembi
    T. Vetrík
    Acta Mathematica Hungarica, 2017, 152 : 11 - 24
  • [35] A NOTE ON EDGE-CONNECTIVITY OF THE CARTESIAN PRODUCT OF GRAPHS
    Fitina, Lakoa
    Lenard, C. T.
    Mills, T. M.
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2011, 84 (01) : 171 - 176
  • [36] On two conjectures of Randic index and the largest signless Laplacian eigenvalue of graphs
    Deng, Hanyuan
    Balachandran, S.
    Ayyaswamy, S. K.
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2014, 411 (01) : 196 - 200
  • [37] k-factors in regular graphs and edge-connectivity
    Kimura, Kenji
    Aldred, R.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2008, 5 (01) : 61 - 71
  • [38] On the Laplacian and signless Laplacian polynomials of graphs with semiregular automorphisms
    Arezoomand, Majid
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2020, 52 (01) : 21 - 32
  • [39] Matching and edge-connectivity in graphs with given maximum degree
    Henning, Michael A.
    Yeo, Anders
    DISCRETE MATHEMATICS, 2021, 344 (08)
  • [40] l $\ell $-Connectivity and l $\ell $-edge-connectivity of random graphs
    Gu, Ran
    Gu, Xiaofeng
    Shi, Yongtang
    Wang, Hua
    JOURNAL OF GRAPH THEORY, 2022, 101 (01) : 5 - 28