On non-essential edges in 3-connected graphs
type: Item
instance of: scholarly article
title: On non-essential edges in 3-connected graphs
zbMATH Open document ID: 0963.05084
author: Talmage James Reid
author: Haidong Wu
published in: Graphs and Combinatorics
publication date: 2001-06-21T00:00:00Z
review text: An edge \(e\) in a simple 3-connected graph is deletable (contractible), if the deletion \(G-e\) (contraction \(G/e\)) is still simple and 3-connected. Let \(a,b\), and \(c\) be three non-negative integers. If there exists a simple 3-connected graph with exactly \(a\) edges which are deletable but not contractible, exactly \(b\) edges which are contractible but not deletable, and exactly \(c\) edges which are both deletable and contractible, then the triple \((a,b,c)\) is called realizable, and such a graph is said to be an \((a,b,c)\)-graph. Tutte's classical wheels theorem [Nederl. Akad. Wet., Proc., Ser. A 64, 441-455 (1961; Zbl 0101.40903)] says that the only (0, 0, 0)-graphs are the wheels. Using Tutte's wheels theorem, the authors characterize the \((a,b,c)\) realizable triples for which at least one of \(a+b\leq 2\), \(c=0\), and \(c\geq 16\) holds.
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1529291
zbMATH Keywords: 3-connected graphs
zbMATH Keywords: Tutte's wheels theorem
MaRDI profile type: Publication
full work available at URL: s003730070015
OpenAlex ID: W1991339404
DOI: 10.1007/S003730070015
Recommended article: The 3-connected graphs with exactly three non-essential edges
Recommended article: The 3-connected graphs with exactly \(k\) non-essential edges
Recommended article: Q3758870
Recommended article: Q5422997
Recommended article: Non-contractible edges in a 3-connected graph
Recommended article: Contractible non-edges in \(3\)-connected graphs
Recommended article: Non removable edges in 3-connected cubic graphs
Recommended article: On \(3^*\)-connected graphs
Recommended article: Q3781783
Recommended article: Q4820536
description: scientific article; zbMATH DE number 1529291