0000000000011572
AUTHOR
Nicolas Gastineau
showing 14 related works from this author
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
Distributed Leader Election and Computation of Local Identifiers for Programmable Matter
2019
International audience; The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(…
Subdivision into i-packings and S-packing chromatic number of some lattices
2015
An ?$i$?-packing in a graph ?$G$? is a set of vertices at pairwise distance greater than ?$i$?. For a nondecreasing sequence of integers ?$S=(s_1,s_2,\ldots)$?, the?$S$?-packing chromatic number of a graph ?$G$? is the least integer ?$k$? such that there exists a coloring of ?$G$? into ?$k$? colors where each set of vertices colored ?$i$?, ?$i=1,\ldots,k$?, is an ?$s_i$?-packing. This paper describes various subdivisions of an ?$i$?-packing into ?$j$?-packings ?$(j>i)$? for the hexagonal, square and triangular lattices. These results allow us to bound the ?$S$?-packing chromatic number for these graphs, with more precise bounds and exact values for sequences ?$S=(s_i,i \in \mathbb{N}^*)$?, …
Dichotomies properties on computational complexity of S-packing coloring problems
2015
This work establishes the complexity class of several instances of the S -packing coloring problem: for a graph G , a positive integer k and a nondecreasing list of integers S = ( s 1 , ? , s k ) , G is S -colorable if its vertices can be partitioned into sets S i , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.
Completely independent spanning trees in some regular graphs
2014
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…
On the family ofr-regular graphs with Grundy numberr+1
2014
Abstract The Grundy number of a graph G , denoted by Γ ( G ) , is the largest k such that there exists a partition of V ( G ) , into k independent sets V 1 , … , V k and every vertex of V i is adjacent to at least one vertex in V j , for every j i . The objects which are studied in this article are families of r -regular graphs such that Γ ( G ) = r + 1 . Using the notion of independent module, a characterization of this family is given for r = 3 . Moreover, we determine classes of graphs in this family, in particular, the class of r -regular graphs without induced C 4 , for r ≤ 4 . Furthermore, our propositions imply results on the partial Grundy number.
Leader election and local identifiers for three‐dimensional programmable matter
2020
International audience; In this paper, we present two deterministic leader election algorithms for programmable matter on the face-centered cubic grid. The face-centered cubic grid is a 3-dimensional 12-regular infinite grid that represents an optimal way to pack spheres (i.e., spherical particles or modules in the context of the programmable matter) in the 3-dimensional space. While the first leader election algorithm requires a strong hypothesis about the initial configuration of the particles and no hypothesis on the system configurations that the particles are forming, the second one requires fewer hypothesis about the initial configuration of the particles but does not work for all pos…
Packing colorings of subcubic outerplanar graphs
2018
Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…
On the family of $r$-regular graphs with Grundy number $r+1$
2014
International audience; The Grundy number of a graph $G$, denoted by $\Gamma(G)$, is the largest $k$ such that there exists a partition of $V(G)$, into $k$ independent sets $V_1,\ldots, V_k$ and every vertex of $V_i$ is adjacent to at least one vertex in $V_j$, for every $j < i$. The objects which are studied in this article are families of $r$-regular graphs such that $\Gamma(G) = r + 1$. Using the notion of independent module, a characterization of this family is given for $r=3$. Moreover, we determine classes of graphs in this family, in particular the class of $r$-regular graphs without induced $C_4$, for $r \le 4$. Furthermore, our propositions imply results on partial Grundy number.
Almost disjoint spanning trees
2016
International audience; In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 ,. .. , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T. We denote by I(T) the set of inner vertices of tree T. The spanning trees T 1 ,. .. , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 ,. .. , T k and the trees T 1 ,. .. , T k are pairwise edge-disjoint. Completely independent spanning trees were introduced by Hasunuma [4] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [4], maxim…
Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers
2014
International audience; Nous étudions l'existence de $r$ arbres couvrants complètement indépendants dans des graphes $2r$-réguliers et $2r$-connexes, et énonçons des conditions nécessaires à leur existence. Nous déterminons le nombre maximum d'arbres dans les produits cartésiens d'une clique et d'un cycle. Nous montrons que ce nombre n'est pas toujours $r$.
Packing coloring and subsets preserving path distance
2016
International audience
Partitionability, coverability and colorability in graphs
2014
Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each ji. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a cla…
On parameterized complexity to determine b-chromatic and partial Grundy numbers
2014
International audience