Toughness Properties of Arbitrarily Partitionable Graphs - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport Année : 2023

Toughness Properties of Arbitrarily Partitionable Graphs


Drawing inspiration from a well-known conjecture of Chv\'atal on a toughness threshold guaranteeing graph Hamiltonicity, we investigate 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, we provide constructions of non-AP graphs with toughness about $\frac{5}{4}$, \textit{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|$. We also consider side related questions on graphs that can be partitioned arbitrarily into only a few connected graphs (with arbitrary orders). Among other things, we prove that not all $1$-tough graphs can always be partitioned into four connected graphs this way. As going along, we also raise several other questions and problems of interest on the topic.
Fichier principal
Vignette du fichier
ap-tough.pdf (405.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04312057 , version 1 (28-11-2023)


  • HAL Id : hal-04312057 , version 1


Julien Bensmail. Toughness Properties of Arbitrarily Partitionable Graphs. Université côte d'azur. 2023. ⟨hal-04312057⟩
36 Consultations
11 Téléchargements


Gmail Facebook X LinkedIn More