Contractible Edges in k-Connected Infinite Graphs.pdf
需积分: 5 93 浏览量
2023-07-09
19:41:52
上传
评论
收藏 458KB PDF 举报
Graphs and Combinatorics
DOI 10.1007/s00373-017-1842-z
ORIGINAL PAPER
Contractible Edges in k-Connected Infinite Graphs
Tsz Lung Chan
1
Received: 22 June 2016 / Revised: 28 February 2017
© Springer Japan KK 2017
Abstract In this paper, we prove that every vertex in a k-connected locally finite
graph (k ≥ 2) which is triangle-free or has minimum degree greater than
3
2
(k − 1)
is incident to at least two contractible edges. Also, it is shown that every vertex in
a k-connected locally finite graph (k ≥ 3) with no adjacent triangles is incident to
a contractible edge. By restricting to graphs with large minimum end vertex-degree,
we generalize Egawa’s result (Graphs Comb 7:15–21, 1991) and prove that every k-
connected locally finite infinite graph such that the minimum degree is at least
5k
4
and all ends have vertex-degree greater than k contains a contractible edge. We also
generalize Dean’s result (J Comb Theory Ser B 48:1–5, 1990) and prove that for any
k-connected locally finite infinite graph G (k ≥ 4) with minimum end vertex-degree
greater than k which is triangle-free or has minimum degree at least
3k
2
, the closure of
the subgraph induced by all the contractible edges in the Freudenthal compactification
of G is topologically 2-connected.
Keywords Contractible edge · k-connected graph · Infinite graph
Mathematics Subject Classification 05C40 · 05C63
1 Introduction
Thomassen [20] proved the existence of contractible edges in any k-connected triangle-
free finite graphs. Later, Egawa et al. [14] generalized Thomassen’s result and proved
that every k-connected triangle-free finite graph G contains at least min{|V (G)|
+
3
2
k
2
− 3k, |E (G)|} contractible edges. Dean [8] studied the distribution of con-
B
Tsz Lung Chan
tlchantl@gmail.com
1
Mathematisches Seminar, Universität Hamburg, Bundesstraße 55, 20146 Hamburg, Germany
123
资源评论
