Removable edges in 3‐connected graphs

Derek A. Holton, Bill Jackson, Akira Saito, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

23 Citations (Scopus)

Abstract

An edge e of a 3‐connected graph G is said to be removable if G ‐ e is a subdivision of a 3‐connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3‐connected graphs and prove that a 3‐connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.

Original languageEnglish
Pages (from-to)465-473
Number of pages9
JournalJournal of Graph Theory
Volume14
Issue number4
DOIs
Publication statusPublished - 1990
Externally publishedYes

Cite this