ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


J. Wu, H. Broersma, Y. Mao and Q. Ma


Removable edges on a Hamilton cycle or outside a cycle in a 4-connected graph


Discussiones Mathematicae Graph Theory

Received: 2018-07-11, Revised: 2018-12-23, Accepted: 2019-02-09,


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.


4-connected graph, removable edge, fragment, atom