We deal with global communication on connected graphs. First, we consider the case of the total exchange. The minimum total exchange time (M.T.E.T.) is the minimum number of steps required to fully inform all the vertices. We establish new bounds (lower and upper) on the M.T.E.T. We determine the M.T.E.T. of the trees and more generally of the...
-
December 15, 2003 (v1)PublicationUploaded on: December 4, 2022
-
July 10, 2007 (v1)Conference paper
Bermond-Thomassen conjecture says that a digraph of minimum out-degree at least 2r−1, r >=1, contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, but it is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for...
Uploaded on: February 28, 2023 -
December 8, 2017 (v1)Journal article
In this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $k \geq 1$, every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ has~$k$ vertex-disjoint cycles of different...
Uploaded on: February 28, 2023