Toughness of Recursively Partitionable Graphs

DOI10.20429/TAG.2023.10204zbMATH Open1530.05147arXiv2210.10590OpenAlexW4389994590MaRDI QIDQ6147455FDOQ6147455

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)

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.

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

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

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)

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)