A σ3 condition for arbitrarily partitionable graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discussiones Mathematicae Graph Theory Année : 2024

A σ3 condition for arbitrarily partitionable graphs

Résumé

A graph $G$ of order $n$ is arbitrarily partitionable (AP for short) if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ such that $G[V_i]$ is a connected graph of order $\lambda_i$ for every $i \in \{1,\dots,p\}$. Several aspects of AP graphs have been investigated to date, including their connection to Hamiltonian graphs and traceable graphs. Every traceable graph (and, thus, Hamiltonian graph) is indeed known to be AP, and a line of research on AP graphs is thus about weakening, to APness, known sufficient conditions for graphs to be Hamiltonian or traceable. In this work, we provide a sufficient condition for APness involving the parameter $\overline{\sigma_3}$, where, for a given graph $G$, the parameter $\overline{\sigma_3}(G)$ is defined as the minimum value of $d(u)+d(v)+d(w)-|N(u) \cap N(v) \cap N(w)|$ for a set $\{u,v,w\}$ of three pairwise independent vertices $u$, $v$, and $w$ of $G$. Flandrin, Jung, and Li proved that any graph $G$ of order $n$ is Hamitonian provided $G$ is $2$-connected and $\overline{\sigma_3}(G) \geq n$, and traceable provided $\overline{\sigma_3}(G) \geq n-1$. Unfortunately, we exhibit examples showing that having $\overline{\sigma_3}(G) \geq n-2$ is not a guarantee for $G$ to be AP. However, we prove that $G$ is AP provided $G$ is $2$-connected, $\overline{\sigma_3}(G) \geq n-2$, and $G$ has a perfect matching or quasi-perfect matching.
Fichier principal
Vignette du fichier
sigma3ap.pdf (293.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03665116 , version 1 (11-05-2022)
hal-03665116 , version 2 (28-07-2022)

Identifiants

Citer

Julien Bensmail. A σ3 condition for arbitrarily partitionable graphs. Discussiones Mathematicae Graph Theory, 2024, 44 (2), pp.755-776. ⟨10.7151/dmgt.2471⟩. ⟨hal-03665116v2⟩
93 Consultations
58 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More