Toughness properties of arbitrarily partitionable graphs
Drawing inspiration from a well-known conjecture of \textit{V. Chvátal} [Discrete Math. 5, 215--228 (1973; Zbl 0256.05122)] on a toughness threshold guaranteeing graph Hamiltonicity, in this paper, the author investigates toughness properties of so-called arbitrarily partitionable (AP) graphs, which are those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders, and can be perceived as a weakening of Hamiltonian and traceable graphs. In particular, the author provides constructions of non-AP graphs with toughness about \(\frac{5}{4},\) i.e., in which, when removing the vertices of any cut-set \(S,\) the number of resulting connected components is at most about \(\frac{4}{5}|S|.\) Further, the author considers side related questions on graphs that can be partitioned arbitrarily into only a few connected graphs (with arbitrary orders). Among other things, it is proved that not all 1-tough graphs can always be partitioned into four connected graphs this way.
- A _3 condition for arbitrarily partitionable graphs
- A degree bound on decomposable trees
- A homology theory for spanning tress of a graph
- An Ore-type condition for arbitrarily vertex decomposable graphs
- Decomposable trees: A polynomial algorithm for tripodes
- Dense arbitrarily partitionable graphs
- Dense arbitrarily vertex decomposable graphs
- Fully decomposable split graphs
- Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
- scientific article; zbMATH DE number 3668667 (Why is no real title available?)
- scientific article; zbMATH DE number 3603293 (Why is no real title available?)
- scientific article; zbMATH DE number 5238175 (Why is no real title available?)
- More aspects of arbitrarily partitionable graphs
- Not every 2-tough graph is Hamiltonian
- Note on Hamilton Circuits
- On arbitrarily vertex decomposable trees
- On the complexity of partitioning a graph into a few connected subgraphs
- On the structure of arbitrarily partitionable graphs with given connectivity
- On three polynomial kernels of sequences for arbitrarily partitionable graphs
- Partitioning Harary graphs into connected subgraphs containing prescribed vertices
- Partitioning powers of traceable or Hamiltonian graphs
- Structural properties of recursively partitionable graphs with connectivity 2
- The Factorization of Locally Finite Graphs
- Tough graphs and Hamiltonian circuits.
- Toughness and the existence ofk-factors
- Toughness in graphs -- a survey
- Toughness, hamiltonicity and split graphs
- Toughness, minimum degree, and the existence of 2‐factors
This page was built for publication: Toughness properties of arbitrarily partitionable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906739)
