Properties of uniformly \(3\)-connected graphs
type: Item
instance of: scholarly article
title: Properties of uniformly \(3\)-connected graphs
zbMATH Open document ID: 1547.05151
author: Frank Göring
author: Tobias Hofmann
published in: Discrete Mathematics and Theoretical Computer Science. DMTCS
publication date: 2024-09-06T00:00:00Z
review text: A graph on at least \(k+1\) vertices is uniformly \(k\)-connected if each pair of its vertices is connected by \(k\) and not more than \(k\) independent paths. The paper shows how the number of vertices of a uniformly 3-connected graph depends on the operations involved in constructing it. Furthermore, the authors show that the bridge operation preserves in a sense crossing numbers and under certain conditions treewidths larger than two, and demonstrate how the results can be used to find out when extremal uniformly 3-connected graphs are planar.
reviewed by: Hang Lau
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 7908431
zbMATH Keywords: uniform connectivity
zbMATH Keywords: graph constructions
zbMATH Keywords: crossing number
zbMATH Keywords: treewidth
zbMATH Keywords: vertices of minimum degree
MaRDI profile type: Publication
cites work: Coloring Graphs with Constraints on Connectivity
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: The average connectivity of a graph
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: On interval routing schemes and treewidth
cites work: Graph Classes: A Survey
cites work: Q5272625
cites work: A theorem on n-connected graphs
cites work: The treewidth of line graphs
cites work: Zur Struktur minimal n-fach zusammenhängender Graphen
cites work: The challenges of unbounded treewidth in parameterised subgraph counting problems
cites work: Q3284374
cites work: Q5524326
DOI: 10.46298/DMTCS.10407
description: scientific article; zbMATH DE number 7908431