On maximum critically h-connected graphs
type: Item
instance of: scholarly article
title: On maximum critically h-connected graphs
zbMATH Open document ID: 0553.05049
DOI: 10.1016/0012-365X(84)90083-9
author: H. J. Krol
author: Henk Jan Veldman
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: Fix the integer \(h\geq 2\). An h-connected graph G is said to be critically h-connected in G-v has connectivity h-1 for \(v\in V(G)\). Denote by \({\mathcal C}\) the set of all critically h-connected graphs and by \({\mathcal A}\) the subset of \({\mathcal C}\) of those graphs in which each vertex is adjacent to a vertex with degree h. Let \(\hat {\mathcal C}\) and \(\hat {\mathcal A}\) be the subsets of \({\mathcal C}\) and \({\mathcal A}\), respectively, containing those graphs which, for given order, have the maximum number of edges. The authors determine \(\hat {\mathcal A}\) for \(h\geq 2\). It follows from the reviewer's characterization of \(\hat {\mathcal C}\) for \(h=2\) that \(\hat {\mathcal A}\neq \hat {\mathcal C}\) in this case. In contrast, the authors show that \(\hat {\mathcal A}=\hat {\mathcal C}\) for \(h=3\) and conjecture that this is so for \(h>3\) also.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 3880751
zbMATH Keywords: critical connected graphs
zbMATH Keywords: degree
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Characterization of maximum critically 2-connected graphs
cites work: Parallel concepts in graph theory
cites work: Non-\(\kappa\)-critical vertices in graphs
full work available at URL: 0012-365x(84)90083-9
OpenAlex ID: W2019198093
Recommended article: Q3415401
Recommended article: Q3469117
Recommended article: Q3974321
Recommended article: Q3538390
Recommended article: Maximam critical n-edge connected graph
Recommended article: Q3720631
Recommended article: Characteristics of maximum critically \(h\)-connected graphs of order \(n\) when \(h\geq n/2\)
Recommended article: Q3974327
Recommended article: Q3572920
Recommended article: Q4294629
description: scientific article; zbMATH DE number 3880751