Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

A σ3 condition for arbitrarily partitionable graphs

Julien Bensmail 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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 maximum 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 $\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.
Document type :
Reports
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03665116
Contributor : Julien Bensmail Connect in order to contact the contributor
Submitted on : Wednesday, May 11, 2022 - 2:31:10 PM
Last modification on : Friday, May 13, 2022 - 3:37:11 AM

File

sigma3ap.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03665116, version 1

Collections

Citation

Julien Bensmail. A σ3 condition for arbitrarily partitionable graphs. [Research Report] Université côte d'azur. 2022. ⟨hal-03665116⟩

Share

Metrics

Record views

13

Files downloads

16