Contractible and Removable Edges in 3-Connected Infinite Graphs

被引:1
|
作者
Chan, Tsz Lung [1 ]
机构
[1] Univ Hamburg, Math Seminar, D-20146 Hamburg, Germany
关键词
Contractible edge; Removable edge; 3-connected graph; Infinite graph; CYCLES;
D O I
10.1007/s00373-014-1431-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Several results concerning contractible and removable edges in 3-connected finite graphs are extended to infinite graphs. First, we prove that every 3-connected locally finite infinite graph has infinitely many removable edges. Next, we prove that for any 3-connected graph , if is a finite degree vertex in and is not incident to any contractible edges, then is a finite cycle or contains a border pair. As a result, every 3-connected locally finite infinite graph contains infinitely many contractible edges. Lastly, it is shown that for any 3-connected locally finite infinite graph which is triangle-free or has minimum degree at least 4, the closure of the subgraph induced by all the contractible edges in the Freudenthal compactification of is topologically 2-connected.
引用
收藏
页码:871 / 883
页数:13
相关论文
共 50 条
  • [31] On the number of 4-contractible edges in 4-connected graphs
    Ando, K.
    Egawa, Y.
    Kawarabayashi, K.
    Kriesell, Matthias
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (01) : 97 - 109
  • [32] Contractible edges of k-connected graphs for k=4, 5
    Qin, Chengfu
    Guo, Xiaofeng
    ARS COMBINATORIA, 2010, 97 : 321 - 332
  • [33] Removable edges in a k-connected graph and a construction method for k-connected graphs
    Su, Jianji
    Guo, Xiaofeng
    Xu, Liqiong
    DISCRETE MATHEMATICS, 2009, 309 (10) : 3161 - 3165
  • [34] Removable edges in a 5-connected graph and a construction method of 5-connected graphs
    Xu, Liqiong
    Guo, Xiaofeng
    DISCRETE MATHEMATICS, 2008, 308 (09) : 1726 - 1731
  • [35] NONSEPARATING INDUCED CYCLES CONSISTING OF CONTRACTIBLE EDGES IN k-CONNECTED GRAPHS
    Egawa, Yoshimi
    Inoue, Katsumi
    Kawarabayashi, Ken-Ichi
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 21 (04) : 1061 - 1070
  • [36] Removable edges in Halin graphs
    Wang, Yan
    Deng, Jiahong
    Lu, Fuliang
    DISCRETE APPLIED MATHEMATICS, 2024, 349 : 1 - 7
  • [37] Cycles having the same modularity and removable edges in 2-connected graphs
    Ando, K
    Hagita, M
    Kaneko, A
    Kano, M
    Kawarabayashi, K
    Saito, A
    DISCRETE MATHEMATICS, 2003, 265 (1-3) : 23 - 30
  • [38] Cycles through 4 vertices in 3-connected graphs
    Lv, Xuezheng
    Yi, Chengdong
    DISCRETE MATHEMATICS, 2009, 309 (01) : 64 - 76
  • [39] A Survey on Contractible Edges in Graphs of a Prescribed Vertex Connectivity
    Matthias Kriesell
    Graphs and Combinatorics, 2002, 18 : 1 - 30
  • [40] Bicritical graphs without removable edges
    Zhang, Yipei
    Wang, Xiumei
    Yuan, Jinjiang
    DISCRETE APPLIED MATHEMATICS, 2022, 320 : 1 - 10