Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph

Jichang Wu, Hajo Broersma, Yaping Mao, Qin Ma*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

70 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)559-587
Number of pages29
JournalDiscussiones Mathematicae - Graph Theory
Volume41
Issue number2
DOIs
Publication statusPublished - 1 May 2021

Keywords

  • 4-Connected graph
  • Atom
  • Fragment
  • Removable edge

Fingerprint

Dive into the research topics of 'Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph'. Together they form a unique fingerprint.

Cite this