SAMPAIO , Rudini

A set C ⊆ V (G) is an identifying code in a graph G if for all v ∈ V (G), C[v] = ∅, and for all distinct u, v ∈ V (G), C[u] = C[v], where C[v] = N [v] ∩ C and N [v] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we study the density of king grids which are strong...

A set C ⊆ V (G) is an identifying code in a graph G if for all v ∈ V (G), C[v] = ∅, and for all distinct u, v ∈ V (G), C[u] = C[v], where C[v] = N [v] ∩ C and N [v] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we study the density of king grids which are strong...

Let G T be the infinite triangular grid. For any positive integer k, we denote by T k the subgraph of G T induced by the vertex set {(x, y) ∈ Z × [k]}. A set C ⊂ V (G) is an identifying code in a graph G if for all v ∈ V (G), N [v] ∩ C = ∅, and for all u, v ∈ V (G), N [u]∩C = N [v]∩C, where N [x] denotes the closed neighborhood of x in G. The...

Let G be a graph G. The neighborhood of a vertex v in G, denoted by N (v), is the set of vertices adjacent to v i G. It closed neighborhood is the set N [v] = N (v) ∪ {v}. A set C ⊆ V (G) is an identifying code in G if (i) for all v ∈ V (G), N [v] ∩ C = ∅, and (ii) for all u, v ∈ V (G), N [u] ∩ C = N [v] ∩ C.In this paper, we give some bounds...

Let $\mathcal{G}_T$ be the infinite triangular grid. For any positive integer $k$, we denote by $T_k$ the subgraph of $\mathcal{G}_T$ induced by the vertex set $\{(x,y)\in\mathbb{Z}\times[k]\}$.A set $C\subset V(G)$ is an {\it identifying code} in a graph $G$ if for all $v\in V(G)$, $N[v]\cap C\neq \emptyset$, and for all $u,v\in V(G)$,...

Given a graph $G$ and a spanning subgraph $T$ of $G$, a backbone $k$-coloring for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$. The backbone chromatic number $\chi_{bb}(G,T)$ is the smallest integer $k$ such that there...

Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$. The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that...

A harmonious k-coloring of a graph G is a 2-distance proper k-coloring of its vertices such that each edge is uniquely identified by the colors of its endpoints. Here, we introduce its game version: the harmonious coloring game. In this two-player game, Alice and Bob alternately select an uncolored vertex and assigns to it a color in {1, . . ....

Given a graph G = (V;E), a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of V(G) colored j has a neighbor with color i. The greatest k such that G has a greedy coloring with k colors is the Grundy number of G. A b-coloring of G is a proper coloring such that every color class contains a vertex...

Given a graph G = (V;E), a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of V(G) colored j has a neighbor with color i. The greatest k such that G has a greedy coloring with k colors is the Grundy number of G. A b-coloring of G is a proper coloring such that every color class contains a vertex...

Les jeux combinatoires à deux joueurs impliquant des agents mobiles dans les graphes (e.g., jeu des gendarmes et du voleur, jeu du dominant éternel, etc.) ont été beaucoup étudiés car ils permettent, d'une part, de comprendre comment coordonner des individus afin de réaliser une tâche commune, et d'autre part d'étudier les propriétés...

We define and study the following two-player game on a graph G. Let k ∈ N *. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s ∈ N * is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same...

We define and study the following two-player game on a graph G. Let k ∈ N *. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s ∈ N * is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same...

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P4-tidy graphs and (q,q − 4)-graphs, for every fixed q. These classes include cographs, P4-sparse and P4-lite graphs. We also obtain a polynomial time algorithm to determine the Grundy...