Browsing by Author "Bensmail, Julien"

Now showing 1 - 4 of 4

Access status: Open Access ,
Closure results for arbitrarily partitionable graphs
(Wydawnictwa AGH, 2024) Bensmail, Julien
A well-known result of Bondy and Chvátal establishes that a graph of order $n$ is Hamiltonian if and only if its $n$-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least $n$) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of Hamiltonian graphs being those graphs that can be partitioned into arbitrarily many connected graphs of arbitrary orders. Among other results, we establish closure results for arbitrary partitions into connected graphs of order at most 3, for arbitrary partitions into connected graphs of order exactly any $\lambda$, and for the property of being arbitrarily partitionable in full.
Access status: Open Access ,
On locally irregular decompositions of subcubic graphs
(Wydawnictwa AGH, 2018) Baudon, Olivier; Bensmail, Julien; Hocquard, Hervé; Senhaji, Mohammed; Sopena, Éric
A graph $G$ is locally irregular if every two adjacent vertices of $G$ have different degrees. A locally irregular decomposition of $G$ is a partition $E_1,\dots,E_k$ of $E(G)$ such that each $G[E_{i}]$ is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than $\frac{12}{5}$. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.
Access status: Open Access ,
On the longest path in a recursively partitionable graph
(2013) Bensmail, Julien
A connected graph $G$ with order $n \geq 1$ is said to be recursively arbitrarily partitionable (R-AP for short) if either it is isomorphic to $K_1$, or for every sequence $(n_1, \ldots , n_p)$ of positive integers summing up to n there exists a partition $(V_1, \ldots , V_p)$ of $V(G)$ such that each $V_i$ induces a connected R-AP subgraph of $G$ on $n_i$ vertices. Since previous investigations, it is believed that a R-AP graph should be »almost traceable« somehow. We first show that the longest path of a R-AP graph on $n$ vertices is not constantly lower than $n$ for every $n$. This is done by exhibiting a graph family $C$ such that, for every positive constant $c \geq 1$, there is a R-AP graph in $C$ that has arbitrary order $n$ and whose longest path has order $n-c$. We then investigate the largest positive constant $c' \lt 1$ such that every R-AP graph on n vertices has its longest path passing through $n \cdot c'$ vertices. In particular, we show that $c' \leq \frac{2}{3}.$ This result holds for R-AP graphs with arbitrary connectivity.
Access status: Open Access ,
Some remarks and results on the Standard (2,2)-Conjecture
(Wydawnictwa AGH, 2026) Baudon, Olivier; Bensmail, Julien; Vayssieres, Lyn
In this note, we prove that every graph can be edge-labelled with red labels $1,2$ and blue labels $1,2$ so that vertices with any sum of incident red labels induce a $1$-degenerate graph, while vertices with any sum of incident blue labels induce a $0$-degenerate graph. This result stands as a closer step towards the so-called Standard $(2,2)$-Conjecture (stating that $0$-degeneracy can be achieved in both colours), and provides some insight on the surrounding field, which covers the 1-2-3 Conjecture, the 1-2 Conjecture, and other close problems. Along the way, we also describe how many related problems are interconnected, and raise new problems and questions for further work on the topic.