Critically \((k,k)\)-connected graphs
type: Item
instance of: scholarly article
title: Critically \((k,k)\)-connected graphs
zbMATH Open document ID: 0629.05042
DOI: 10.1016/0012-365X(87)90114-2
author: Kiyoshi Ando
author: Yoko Usami
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A graph G, with vertex connectivity \(\kappa(G)\), minimum degree \(\delta(G)\), and complement \(\bar G,\) is critically \((k,k)\)-connected if \(\kappa(G)=\kappa(\bar G)=k\), and for each vertex v of G, either \(\kappa(G-v)=k-1\) or \(\kappa(\bar G-v)=k-1\). Theorem: If G is a critically \((k,k)\)-connected graph with \(k\geq 2\), \(\delta(G)\geq (3k-1)\), and \(\delta(\bar G)\geq (3k-1)\), then 3k\(\leq | V(G)| \leq 4k\). Moreover, it is also shown that the upper bound is sharp for \(k\geq 3\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4023323
zbMATH Keywords: critically (k,k)-connected graph
reviewed by: S. F. Kapoor
MaRDI profile type: Publication
cites work: Critically n-Connected Graphs
cites work: On critically h-connected simple graphs
cites work: Eine Eigenschaft der Atome endlicher Graphen
cites work: Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
full work available at URL: 0012-365x(87)90114-2
OpenAlex ID: W2078675358
description: scientific article; zbMATH DE number 4023323