Uniformly connected graphs

In this article we investigate the structure of uniformly \(k\)-connected and uniformly \(k\)-edge-connected graphs. Whereas both types have previously been studied independent of each other, we analyze relations between these two classes. We prove that any uniformly \(k\)-connected graph is also un...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-03
Main Authors: Göring, Frank, Hofmann, Tobias, Streicher, Manuel
Format: Article
Language:English
Subjects:
Apexes
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we investigate the structure of uniformly \(k\)-connected and uniformly \(k\)-edge-connected graphs. Whereas both types have previously been studied independent of each other, we analyze relations between these two classes. We prove that any uniformly \(k\)-connected graph is also uniformly \(k\)-edge-connected for \(k\le 3\) and demonstrate that this is not the case for \(k>3\). Furthermore, uniformly \(k\)-connected and uniformly \(k\)-edge-connected graphs are well understood for \(k\le 2\) and it is known how to construct uniformly \(3\)-edge-connected graphs. We contribute here a constructive characterization of uniformly \(3\)-connected graphs that is inspired by Tuttes Wheel Theorem. Eventually, these results help us to prove a tight bound on the number of vertices of minimum degree in uniformly \(3\)-connected graphs.
ISSN:2331-8422