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 条
  • [41] On the edge-connectivity of graphs with two orbits of the same size
    Yang, Weihua
    Zhang, Zhao
    Guo, Xiaofeng
    Cheng, Eddie
    Liptak, Laszlo
    DISCRETE MATHEMATICS, 2011, 311 (16) : 1768 - 1777
  • [42] The restricted edge-connectivity of de Bruijn undirected graphs
    Xu, Jun-Ming
    Lu, Min
    Fan, Ying-Mei
    ARS COMBINATORIA, 2007, 83 : 321 - 333
  • [43] Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity
    Ok, Seongmin
    Richter, R. Bruce
    Thomassen, Carsten
    GRAPHS AND COMBINATORICS, 2016, 32 (06) : 2575 - 2589
  • [44] The p-restricted edge-connectivity of Kneser graphs
    Balbuena, C.
    Marcote, X.
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 343 : 258 - 267
  • [45] Increasing the edge-connectivity by contracting a vertex subset in graphs
    Nagamochi, H
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2006, E89D (02): : 744 - 750
  • [46] On the minimum degree, edge-connectivity and connectivity of power graphs of finite groups
    Panda, Ramesh Prasad
    Krishna, K. V.
    COMMUNICATIONS IN ALGEBRA, 2018, 46 (07) : 3182 - 3197
  • [47] PRESERVING AND INCREASING LOCAL EDGE-CONNECTIVITY IN MIXED GRAPHS
    BANGJENSEN, J
    FRANK, A
    JACKSON, B
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (02) : 155 - 178
  • [48] Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs
    Das, Kinkar Ch.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (10) : 2420 - 2424
  • [49] Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity
    Seongmin Ok
    R. Bruce Richter
    Carsten Thomassen
    Graphs and Combinatorics, 2016, 32 : 2575 - 2589
  • [50] On maximum signless Laplacian Estrada index of graphs with given parameters
    Ellahi, Hamid Reza
    Fath-Tabar, Gholam Hossein
    Gholami, Ahmad
    Nasiri, Ramin
    ARS MATHEMATICA CONTEMPORANEA, 2016, 11 (02) : 381 - 389