TY - JOUR
T1 - Removable edges in a cycle of a 4-connected graph
AU - Wu, Jichang
AU - Li, Xueliang
AU - Wang, Lusheng
PY - 2004/10/28
Y1 - 2004/10/28
N2 - Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting in the graph G - e; second, for all the vertices x of degree 3 in G - e, delete x from G - e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by G ⊖e. If G ⊖e is still 4-connected, then e is called a removable edge of G. In this paper, we investigate the problem on how many removable edges there are in a cycle of a 4-connected graph, and give examples to show that our results are in some sense the best possible. © 2004 Elsevier B.V. All rights reserved.
AB - Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting in the graph G - e; second, for all the vertices x of degree 3 in G - e, delete x from G - e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by G ⊖e. If G ⊖e is still 4-connected, then e is called a removable edge of G. In this paper, we investigate the problem on how many removable edges there are in a cycle of a 4-connected graph, and give examples to show that our results are in some sense the best possible. © 2004 Elsevier B.V. All rights reserved.
KW - 4-Connected graph
KW - Edge-vertex-cut atom
KW - Edge-vertex-cut fragment
KW - Removable edge
UR - http://www.scopus.com/inward/record.url?scp=4644255583&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-4644255583&origin=recordpage
U2 - 10.1016/j.disc.2004.05.015
DO - 10.1016/j.disc.2004.05.015
M3 - 21_Publication in refereed journal
VL - 287
SP - 103
EP - 111
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 1-3
ER -