Catálogo de publicaciones - libros

The so called ( σ , ρ )-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called ( σ , ρ ) -dominating if for every vertex v  ∈  S , | S  ∩  N ( v )| ∈  σ , and for every v  ∉  S , | S  ∩  N ( v )| ∈  ρ , where σ and ρ are sets of nonnegative integers and N ( v ) denotes the open neighborhood of the vertex v in G .) It was known that for any two nonempty finite sets σ and ρ (such that 0 ∉  ρ ), the decision problem whether an input graph contains a ( σ , ρ )-dominating set is NP-complete, but that when restricted to chordal graphs, some polynomial time solvable instances occur. We show that for chordal graphs, the problem performs a complete dichotomy: it is polynomial time solvable if σ , ρ are such that every chordal graph contains at most one ( σ , ρ )-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs ( σ , ρ ) by a structural description, but at least we can provide a recursive algorithm for their recognition. If ρ contains the 0 element, every graph contains a ( σ , ρ )-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-( σ , ρ )-domination problem is NP-complete for chordal graphs whenever ρ contains, besides 0, at least one more integer.

A graph G  = ( V , E ) is a tolerance graph if each vertex v  ∈  V can be associated with an interval of the real line I _ v and a positive real number t _ v in such a way that ( uv ) ∈  E if and only if | I _ v  ∩  I _ u | ≥ min ( t _ v , t _ u ). No algorithm for recognizing tolerance graphs in general is known. In this paper we present an O ( n  +  m ) algorithm for recognizing tolerance graphs that are also bipartite, where n and m are the number vertices and edges of the graph, respectively. We also give a new structural characterization of these graphs based on the algorithm.

We define helicopter cop and robber games with multiple robbers, extending previous research, which only considered the pursuit of a single robber. Our model is defined for robbers that are visible (the cops know their position) and active (able to move at every turn) but is easily adapted to other common variants of the game. The game with many robbers is non-monotone: more cops are needed if their moves are restricted so as to monotonically decrease the space available to the robbers. Because the cops may decide their moves based on the robbers’ current position, strategies in the game are interactive but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game captures a hierarchy of parameters between proper pathwidth and proper treewidth. We give a complete characterization of the parameter for trees and an upper bound for general graphs.

In graph searching, a team of searchers is aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching , the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching . A search strategy that catches any fugitive in such a way that, the part of the graph reachable by the fugitive never grows is called monotone . A priori , monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack. Fomin et al. (2005) introduced an important graph searching variant, called non-deterministic graph searching , that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching is however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-determinisitic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.

It is well known that boundedness of tree-width implies polynomial-time solvability of many algorithmic graph problems. The converse statement is generally not true, i.e., polynomial-time solvability does not necessarily imply boundedness of tree-width. However, in graphs of bounded vertex degree, for some problems, the two concepts behave in a more consistent way. In the present paper, we study this phenomenon with respect to three important graph problems – dominating set, independent dominating set and induced matching – and obtain several results toward revealing the equivalency between boundedness of the tree-width and polynomial-time solvability of these problems in bounded degree graphs.

The class of 2-interval graphs has been introduced for modelling scheduling and allocation problems, and more recently for specific bioinformatics problems. Some of those applications imply restrictions on the 2-interval graphs, and justify the introduction of a hierarchy of subclasses of 2-interval graphs that generalize line graphs: balanced 2-interval graphs, unit 2-interval graphs, and ( x , x )-interval graphs. We provide instances that show that all inclusions are strict. We extend the NP-completeness proof of recognizing 2-interval graphs to the recognition of balanced 2-interval graphs. Finally we give hints on the complexity of unit 2-interval graphs recognition, by studying relationships with other graph classes: proper circular-arc, quasi-line graphs, K _1,5-free graphs, ...

Graph complexity measures like tree-width , clique-width , NLC-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. Rank-width is based on ranks of adjacency matrices of graphs over GF (2). We propose here algebraic operations on graphs that characterize rank-width. For algorithmic purposes, it is important to represent graphs by balanced terms. We give a unique theorem that generalizes several “balancing theorems” for tree-width and clique-width. New results are obtained for rank-width and a variant of clique-width, called m-clique-width .

The k-power graph of a graph G is the graph in which two vertices are adjacent if and only if there is a path between them in G of length at most k . We show that (1.) the k -power graph of a tree has NLC-width at most k  + 2 and clique-width at most $k+2+\max(\lfloor \frac{k}{2}\rfloor -1,0)$ , (2.) the k -leaf-power graph of a tree has NLC-width at most k and clique-width at most $k+ \max(\lfloor \frac{k}{2}\rfloor -2,0)$ , and (3.) the k -power graph of a graph of tree-width l has NLC-width at most ( k  + 1)^ l  + 1− 1 and clique-width at most 2·( k  + 1)^ l  + 1− 2.

NLC-width is a variant of clique-width with many application in graph algorithmic. This paper is devoted to graphs of NLC-width two. After giving new structural properties of the class, we propose a O ( n ^2 m )-time algorithm, improving Johansson’s algorithm [14]. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust O ( n ^2 m )-time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm.

A minimal triangulation of a graph is a chordal graph obtained from adding an inclusion-minimal set of edges to the graph. For permutation graphs, i.e., graphs that are both comparability and cocomparability graphs, it is known that minimal triangulations are interval graphs. We (negatively) answer the question whether every interval graph is a minimal triangulation of a permutation graph. We give a non-trivial characterisation of the class of interval graphs that are minimal triangulations of permutation graphs and obtain as a surprising result that only “a few” interval graphs are minimal triangulations of permutation graphs.