Toughness properties of arbitrarily partitionable graphs (Q6906739)

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.