Toughness of Recursively Partitionable Graphs

DOI10.20429/TAG.2023.10204MaRDI QIDQ6147455zbMATH OpenOpenAlexFDO

Authors Calum Buchanan, Brandon du Preez, K. E. Perry, Puck Rombach

Publication date 15 January 2024

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2210.10590

zbMATH Keywords

minimal 2-connected recursively partitionable graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: A simple graph $G=(V,E)$ on $n$ vertices is said to be recursively partitionable (RP) if $Gsimeq{K}_1$, or if $G$ is connected and satisfies the following recursive property: for every integer partition $a_1,a_2,dots,a_k$ of $n$, there is a partition $A_1,A_2,dots,A_k$ of $V$ such that each $|A_i|=a_i$, and each induced subgraph $G[A_i]$ is RP ($1leqileqk$). We show that if $S$ is a vertex cut of an RP graph $G$ with $|S|geq2$, then $G-S$ has at most $3|S|-1$ components. Moreover, this bound is sharp for $|S|=3$. We present two methods for constructing new RP graphs from old. We use these methods to show that for all positive integers $s$, there exist infinitely many RP graphs with an $s$-vertex cut whose removal leaves $2s+1$ components. Additionally, we prove a simple necessary condition for a graph to have an RP spanning tree, and we characterise a class of minimal 2-connected RP graphs.

Recommendations

• Structural properties of recursively partitionable graphs with connectivity 2
• On the longest path in a recursively partitionable graph
• On the structure of arbitrarily partitionable graphs with given connectivity
• Some properties of minimal arbitrarily partitionable graphs
• Recursively arbitrarily vertex-decomposable graphs

Cited in

(1)

• Closure results for arbitrarily partitionable graphs

This page was built for publication: Toughness of Recursively Partitionable Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6147455)