Geodesic
Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 559-587.

Voir la notice de l'article provenant de la source Library of Science

Let G be a 4-connected graph. We call an edge e of G removable if the following sequence of operations results in a 4-connected graph: delete e from G; if there are vertices with degree 3 in G−e, then for each (of the at most two) such vertex x, delete x from G − e and turn the three neighbors of x into a clique by adding any missing edges (avoiding multiple edges). In this paper, we continue the study on the distribution of removable edges in a 4-connected graph G, in particular outside a cycle of G or in a spanning tree or on a Hamilton cycle of G. We give examples to show that our results are in some sense best possible.
Keywords: 4-connected graph, removable edge, fragment, atom 
@article{DMGT_2021_41_2_a13,
     author = {Wu, Jichang and Broersma, Hajo and Mao, Yaping and Ma, Qin},
     title = {Removable {Edges} on a {Hamilton} {Cycle} or {Outside} a {Cycle} in a {4-Connected} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {559--587},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a13/}
}
TY  - JOUR
AU  - Wu, Jichang
AU  - Broersma, Hajo
AU  - Mao, Yaping
AU  - Ma, Qin
TI  - Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 559
EP  - 587
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a13/
LA  - en
ID  - DMGT_2021_41_2_a13
ER  - 
%0 Journal Article
%A Wu, Jichang
%A Broersma, Hajo
%A Mao, Yaping
%A Ma, Qin
%T Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 559-587
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a13/
%G en
%F DMGT_2021_41_2_a13
Wu, Jichang; Broersma, Hajo; Mao, Yaping; Ma, Qin. Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 559-587. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a13/

[1] K. Ando, Y. Egawa, K. Kawarabayashi and M. Kriesell, On the number of 4-contractible edges in 4-connected graphs, J. Combin. Theory Ser. B 99 (2009) 97–109. doi:10.1016/j.jctb.2008.04.003

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer Graduate Texts in Mathematics, 2008).

[3] D.A. Holton, B. Jackson, A. Saito and N.C. Wormald, Removable edges in 3-connected graphs, J. Graph Theory 14 (1990) 465–473. doi:10.1002/jgt.3190140410

[4] P.J. Slater, A classification of 4-connected graphs, J. Combin. Theory Ser. B 17 (1974) 281–298. doi:10.1016/0095-8956(74)90034-3

[5] J.C. Wu, H.J. Broersma and H. Kang, Removable edges and chords of longest cycles in 3-connected graphs, Graphs Combin. 30 (2014) 743–753. doi:10.1007/s00373-013-1296-x

[6] J.C. Wu, X.L. Li and L.S. Wang, Removable edges in a cycle of a 4-connected graph, Discrete Math. 287 (2004) 103–111. doi:10.1016/j.disc.2004.05.015

[7] J.C. Wu, X.L. Li and J.J. Su, The number of removable edges in a 4-connected graph, J. Combin. Theory Ser. B 92 (2004) 13–40. doi:10.1016/j.jctb.2004.02.003

[8] J.H. Yin, Removable edges in 4-connected graphs and the structures of 4-connected graphs J. Systems Sci. Math. Sci. 19 (1999) 434–438.