The game of cops and robber is a turn-based vertex pursuit game played on a connected graph between a team of cops and a single robber. The cops and the robber move alternately along the edges of the graph. We say that the ...

Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that ...

We propose a new data structure for manipulating graphs, called -graph, which is particularly suited for designing dynamic algorithms. The structure itself is simple, consisting basically of a triple of elements, for each ...

In this work we consider the problem of finding a minimum Ck-transversal (a subset of vertices hitting all the induced chordless cycles with k vertices) in a graph with bounded maximum degree. In particular, we seek for ...

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number t such ...

Let G = (V,E) be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, z = x), unless z = y, go to a ...

In the context of dynamical systems, time series analysis is frequently used to identify the underlying nature of a phenomenon of interest from a sequence of observations. For signals with a self-affine structure, like ...

In this paper we present distributed property-testing algorithms for graph properties in thecongestmodel, with emphasis on testing subgraph-freeness. Testing a graph propertyPmeansdistinguishing graphsG= (V,E)having ...

A biclique of a graph G is an induced complete bipartite graph. A star of G is a biclique contained in the closed neighborhood of a vertex. A star (biclique) k-coloring of G is a k-coloring of G that contains no monochromatic ...