A remark on the connectivity of the complement of a 3-connected graph
type: Item
instance of: scholarly article
title: A remark on the connectivity of the complement of a 3-connected graph
zbMATH Open document ID: 0864.05057
DOI: 10.1016/0012-365X(94)00078-W
author: Kiyoshi Ando
author: Atsushi Kaneko
published in: Discrete Mathematics
publication date: 1996-07-03T00:00:00Z
review text: A finite simple graph \(\Gamma\) is said to be bi-3-connected if both \(\Gamma\) and its complement \(\overline\Gamma\) are 3-connected. A 2-set of vertices whose contraction results in a bi-3-connected graphe is called a bi-contractible pair. The one main result of this paper is that every bi-3-connected graph on at least 22 vertices admits a bi-contractible pair. This result is analogous to one by \textit{W. T. Tutte} [Nederl. Akad. Wet., Proc., Ser. A 64, 441-455 (1961; Zbl 0101.40903)] that every 3-connected graph on at least five vertices admits an edge whose contraction leaves a 3-connected graph. The authors believe their lower bound on the number of vertices to be inessential and conjecture that every bi-3-connected graph admits a bi-contractible pair.
reviewed by: Mark E. Watkins
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 896523
zbMATH Keywords: connectivity
zbMATH Keywords: contraction
zbMATH Keywords: bi-3-connected graphe
zbMATH Keywords: bi-contractible pair
zbMATH Keywords: 3-connected graph
MaRDI profile type: Publication
cites work: Q4187840
cites work: Contractible edges in 3-connected graphs
cites work: Q3284374
full work available at URL: 0012-365x(94)00078-w
OpenAlex ID: W2046641168
description: scientific article; zbMATH DE number 896523