Source author record

Ignacio M. Pelayo

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Information Theory math.IT

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Metric dimension on sparse graphs and its applications to zero forcing sets

The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$ . It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at most the metric dimension of $T$ plus $6c$ . We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset $S$ of black vertices (whereas the other vertices are colored white) of $G$ such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph $G$ , $dim(G)\leq Z(G) + c(G)$ , where $c(G)$ is the number of edges that have to be removed from $G$ to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: $dim(G)\leq Z(G)+6c(G)$ holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.

preprint2015arXiv

On global location-domination in bipartite graphs

A dominating set $S$ of a graph $G$ is called locating-dominating, LD-set for short, if every vertex $v$ not in $S$ is uniquely determined by the set of neighbors of $v$ belonging to $S$ . Locating-dominating sets of minimum cardinality are called $LD$ -codes and the cardinality of an LD-code is the \emph{location-domination number} $λ(G)$ . An LD-set $S$ of a graph $G$ is \emph{global} if it is an LD-set of both $G$ and its complement $\overline{G}$ . The \emph{global location-domination number} $λ_g(G)$ is the minimum cardinality of a global LD-set of $G$ . For any LD-set $S$ of a given graph $G$ , the so-called \emph{S-associated graph} $G^S$ is introduced. This edge-labeled bipartite graph turns out to be very helpful to approach the study of LD-sets in graphs, particularly when $G$ is bipartite. This paper is mainly devoted to the study of relationships between global LD-sets, LD-codes and the location-domination number in a graph $G$ and its complement $\overline{G}$ , when $G$ is bipartite.

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.

preprint2007arXiv

Extremal Graph Theory for Metric Dimension and Diameter

A set of vertices $S$ \emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$ . The \emph{metric dimension} of $G$ is the minimum cardinality of a resolving set of $G$ . Let $\mathcal{G}_{β,D}$ be the set of graphs with metric dimension $β$ and diameter $D$ . It is well-known that the minimum order of a graph in $\mathcal{G}_{β,D}$ is exactly $β+D$ . The first contribution of this paper is to characterise the graphs in $\mathcal{G}_{β,D}$ with order $β+D$ for all values of $β$ and $D$ . Such a characterisation was previously only known for $D\leq2$ or $β\leq1$ . The second contribution is to determine the maximum order of a graph in $\mathcal{G}_{β,D}$ for all values of $D$ and $β$ . Only a weak upper bound was previously known.

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.