Vertex Connectivity of the Second Iterated Line Graphs with small essential edge connectivity

被引:0
|
作者
YehongShao [1 ]
机构
[1] Ohio Univ Southern, Arts & Sci, Ironton, OH 45638 USA
来源
2011 INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATION AND INFORMATION TECHNOLOGY (ICCCIT 2011) | 2011年
关键词
vertex connectivity; essential edge connectivity; iterated line graph;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The line graph of a graph G, denoted by L(G), has E(G) as its vertex set, where two vertices in L(G) are adjacent if and only if the corresponding edges in G have a common vertex. The second iterated line graph of G, written L-2(G), is the line graph of L(G). Let delta(G) be the minimum degree of G. In 2003, Niepel and Knor proved that if G is a 4-connected graph, then the lower bound of the vertex connectivity of L-2(G) is 4 delta(G) - 6. In 2010, it was proved in [4] that the same lower bound can be obtained for essentially 4-edge-connected and 3-connected graphs. In this paper, we determine the lower bounds in terms of the minimum degree for graphs with small essential edge connectivity.
引用
收藏
页码:81 / 84
页数:4
相关论文
共 40 条
  • [21] THE AUGMENTED ZAGREB INDEX, VERTEX CONNECTIVITY AND MATCHING NUMBER OF GRAPHS
    Ali, A.
    Bhatti, A. A.
    Raza, Z.
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2016, 42 (02): : 417 - 425
  • [22] DEPTH OF BINOMIAL EDGE IDEALS IN TERMS OF DIAMETER AND VERTEX CONNECTIVITY
    Jayanthan, A., V
    Sarkar, Rajib
    JOURNAL OF COMMUTATIVE ALGEBRA, 2024, 16 (04) : 411 - 437
  • [23] Separator-based sparsification - II: Edge and vertex connectivity
    Eppstein, D
    Galil, Z
    Italiano, GF
    Spencer, TH
    SIAM JOURNAL ON COMPUTING, 1998, 28 (01) : 341 - 381
  • [24] Deterministic Small Vertex Connectivity in Almost Linear Time
    Saranurak, Thatchaphol
    Yingchareonthawornchai, Sorrachai
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 789 - 800
  • [25] The second largest eigenvalue and vertex-connectivity of regular multigraphs
    Suil, O.
    DISCRETE APPLIED MATHEMATICS, 2020, 279 : 118 - 124
  • [26] On vertex connectivity of zero-divisor graphs of finite commutative rings
    Chattopadhyay, Sriparna
    Patra, Kamal Lochan
    Sahoo, Binod Kumar
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2024, 59 (04) : 955 - 969
  • [27] Vertex-connectivity in periodic graphs and underlying nets of crystal structures
    Eon, Jean-Guillaume
    ACTA CRYSTALLOGRAPHICA A-FOUNDATION AND ADVANCES, 2016, 72 : 376 - 384
  • [28] THE CONNECTIVITY AND THE MODIFIED SECOND MULTIPLICATIVE ZAGREB INDEX OF GRAPHS
    Du, Jianwei
    Sun, Xiaoling
    JOURNAL OF APPLIED MATHEMATICS & INFORMATICS, 2021, 39 (3-4): : 339 - 358
  • [29] THE VERTEX CONNECTIVITY AND THE THIRD LARGEST EIGENVALUE IN REGULAR (MULTI-)GRAPHS
    Ma, Tingyan
    Wang, Ligong
    Hu, Yang
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2024, 40 : 322 - 332
  • [30] Extremal spectral radius and essential edge-connectivity
    Wang, Yu
    Lin, Huiqiu
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2024, 347 (06)