Frank Göring ; Tobias Hofmann - Properties of uniformly $3$-connected graphs

dmtcs:10407 - Discrete Mathematics & Theoretical Computer Science, June 7, 2024, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10407
Properties of uniformly $3$-connected graphsArticle

Authors: Frank Göring ; Tobias Hofmann

    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. We reinvestigate a recent constructive characterization of uniformly $3$-connected graphs and obtain a more detailed result that relates the number of vertices to the operations involved in constructing a respective uniformly $3$-connected graph. Furthermore, we investigate how crossing numbers and treewidths behave under the mentioned constructions. We demonstrate how these results can be utilized to study the structure and properties of uniformly $3$-connected graphs with minimum number of vertices of minimum degree.


    Volume: vol. 25:3 special issue ICGT'22
    Section: Special issues
    Published on: June 7, 2024
    Accepted on: October 19, 2023
    Submitted on: December 1, 2022
    Keywords: Mathematics - Combinatorics,05C40, 05C75, 05C07, 05D99

    Consultation statistics

    This page has been seen 128 times.
    This article's PDF has been downloaded 109 times.