A $\sigma_3$ condition for arbitrarily partitionable graphs

Bensmail, Julien 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 755-776

Résumé

A graph G of order n is arbitrarily partitionable (AP for short) if, for every partition (λ_1, . . . ,λ_p) of n, there is a partition (V_1, . . . ,V_p) of V(G) such that G[V_i] is a connected graph of order λ_i for every i ∈{1, . . .,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 σ_3, where, for a given graph G, the parameter σ_3(G) is defined as the minimum value of d(u)+d(v)+d(w)-|N(u) ∩ N(v) ∩ 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 σ_3(G) ≥ n, and traceable provided σ_3(G) ≥ n-1. Unfortunately, we exhibit examples showing that having σ_3(G) ≥ n-2 is not a guarantee for G to be AP. However, we prove that G is AP provided G is 2-connected, σ_3(G) ≥ n-2, and G has a perfect matching or quasi-perfect matching.

Détail

Keywords: arbitrarily partitionable graph, partition into connected subgraphs, $\sigma_3$ condition, Hamiltonian graph, traceable graph