Source author record

José Cáceres

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Quasi-efficient domination in grids

Domination of grids has been proved to be a demanding task and with the addition of independence it becomes more challenging. It is known that no grid with $m,n \geq 5$ has an efficient dominating set, also called perfect code, that is, an independent vertex set such that each vertex not in it has exactly one neighbor in that set. So it is interesting to study the existence of independent dominating sets for grids that allow at most two neighbors, such sets are called independent $[1,2]$ -sets. In this paper we prove that every grid has an independent $[1,2]$ -set, and we develop a dynamic programming algorithm using min-plus algebra that computes $i_{[1,2]}(P_m\Box P_n)$ , the minimum cardinality of an independent $[1,2]$ -set for the grid graph $P_m\square P_n$ . We calculate $i_{[1,2]}(P_m\Box P_n)$ for $2\leq m\leq 13, n\geq m$ using this algorithm, meanwhile the parameter for grids with $14\leq m\leq n$ is obtained through a quasi-regular pattern that, in addition, provides an independent $[1,2]$ -set of minimum size.

preprint2016arXiv

Shortcut sets for the locus of plane Euclidean networks

We study the problem of augmenting the locus $\mathcal{N}_{\ell}$ of a plane Euclidean network $\mathcal{N}$ by inserting iteratively a finite set of segments, called \emph{shortcut set}, while reducing the diameter of the locus of the resulting network. There are two main differences with the classical augmentation problems: the endpoints of the segments are allowed to be points of $\mathcal{N}_{\ell}$ as well as points of the previously inserted segments (instead of only vertices of $\mathcal{N}$ ), and the notion of diameter is adapted to the fact that we deal with $\mathcal{N}_{\ell}$ instead of $\mathcal{N}$ . This increases enormously the hardness of the problem but also its possible practical applications to network design. Among other results, we characterize the existence of shortcut sets, compute them in polynomial time, and analyze the role of the convex hull of $\mathcal{N}_{\ell}$ when inserting a shortcut set. Our main results prove that, while the problem of minimizing the size of a shortcut set is NP-hard, one can always determine in polynomial time whether inserting only one segment suffices to reduce the diameter.

preprint2015arXiv

Perfect and quasiperfect domination in trees

A $k-$ quasiperfect dominating set ( $k\ge 1$ ) of a graph $G$ is a vertex subset $S$ such that every vertex not in $S$ is adjacent to at least one and at most k vertices in $S$ . The cardinality of a minimum k-quasiperfect dominating set in $G$ is denoted by $γ_{\stackrel{}{1k}}(G)$ . Those sets were first introduced by Chellali et al. (2013) as a generalization of the perfect domination concept. The quasiperfect domination chain $γ_{\stackrel{}{11}}(G)\geγ_{\stackrel{}{12}}(G)\ge\dots\geγ_{\stackrel{}{1Δ}}(G)=γ(G)$ , indicates what it is lost in size when you move towards a more perfect domination. We provide an upper bound for $γ_{\stackrel{}{1k}}(T)$ in any tree $T$ and trees achieving this bound are characterized. We prove that there exist trees satisfying all the possible equalities and inequalities in this chain and a linear algorithm for computing $γ_{\stackrel{}{1k}}(T)$ in any tree is presented.

preprint2014arXiv

On Perfect and Quasiperfect Domination in Graphs

A subset $S\subseteq V$ in a graph $G=(V,E)$ is a $k$ -quasiperfect dominating set (for $k\geq 1$ ) if every vertex not in $S$ is adjacent to at least one and at most $k$ vertices in $S$ . The cardinality of a minimum $k$ -quasiperfect dominating set in $G$ is denoted by $γ_ {\stackrel{}{1k}}(G)$ . Those sets were first introduced by Chellali et al. (2013) as a generalization of the perfect domination concept and allow us to construct a decreasing chain of quasiperfect dominating numbers $n \ge γ_ {\stackrel{}{11}}(G) \ge γ_ {\stackrel{}{12}}(G)\ge \ldots \ge γ_ {\stackrel{}{1Δ}}(G)=γ(G)$ in order to indicate how far is $G$ from being perfectly dominated. In this paper we study properties, existence and realization of graphs for which the chain is short, that is, $γ_ {\stackrel{}{12}}(G)=γ(G)$ . Among them, one can find cographs, claw-free graphs and graphs with extremal values of $Δ(G)$ .

preprint2012arXiv

Locating dominating codes: Bounds and extremal cardinalities

In this work, two types of codes such that they both dominate and locate the vertices of a graph are studied. Those codes might be sets of detectors in a network or processors controlling a system whose set of responses should determine a malfunctioning processor or an intruder. Here, we present our more significant contributions on λ-codes and η-codes concerning concerning bounds, extremal values and realization theorems.

preprint2012arXiv

Resolving sets for Johnson and Kneser graphs

A set of vertices $S$ in a graph $G$ is a {\em resolving set} for $G$ if, for any two vertices $u,v$ , there exists $x\in S$ such that the distances $d(u,x) \neq d(v,x)$ . In this paper, we consider the Johnson graphs $J(n,k)$ and Kneser graphs $K(n,k)$ , and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.