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

Holton, Derek A. ; Jackson, Bill ; Saito, Akira ; Wormald, Nicholas C. / Removable edges in 3‐connected graphs. In: Journal of Graph Theory. 1990 ; Vol. 14, No. 4. pp. 465-473.
@article{1581e98dd5514a73957d30ca7b6d5210,
title = "Removable edges in 3‐connected graphs",
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.",
author = "Holton, {Derek A.} and Bill Jackson and Akira Saito and Wormald, {Nicholas C.}",
year = "1990",
doi = "10.1002/jgt.3190140410",
language = "English",
volume = "14",
pages = "465--473",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "John Wiley & Sons",
number = "4",

}

Removable edges in 3‐connected graphs. / Holton, Derek A.; Jackson, Bill; Saito, Akira; Wormald, Nicholas C.

In: Journal of Graph Theory, Vol. 14, No. 4, 1990, p. 465-473.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Removable edges in 3‐connected graphs

AU - Holton, Derek A.

AU - Jackson, Bill

AU - Saito, Akira

AU - Wormald, Nicholas C.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84986439477&partnerID=8YFLogxK

U2 - 10.1002/jgt.3190140410

DO - 10.1002/jgt.3190140410

M3 - Article

VL - 14

SP - 465

EP - 473

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 4

ER -