Source author record

Carmen Hernando

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

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

New results on metric-locating-dominating sets of graphs

A dominating set $S$ of a graph is a metric-locating-dominating set if each vertex of the graph is uniquely distinguished by its distances from the elements of $S$ , and the minimum cardinality of such a set is called the metric-location-domination number. In this paper, we undertake a study that, in general graphs and specific families, relates metric-locating-dominating sets to other special sets: resolving sets, dominating sets, locating-dominating sets and doubly resolving sets. We first characterize classes of trees according to certain relationships between their metric-location-domination number and their metric dimension and domination number. Then, we show different methods to transform metric-locating-dominating sets into locating-dominating sets and doubly resolving sets. Our methods produce new bounds on the minimum cardinalities of all those sets, some of them involving parameters that have not been related so far.

preprint2016arXiv

On the Partition Dimension and the Twin Number of a Graph

A partition P of the vertex set of a connected graph G is a locating partition of G if every vertex is uniquely determined by its vector of distances to the elements of P. The partition dimension of G is the minimum cardinality of a locating partition of G. A pair of vertices u,v of a graph G are called twins if they have exactly the same set of neighbors other than u and v. A twin class is a maximal set of pairwise twin vertices. The twin number of a graph G is the maximum cardinality of a twin class of G. In this paper we undertake the study of the partition dimension of a graph by also considering its twin number. This approach allows us to obtain the set of connected graphs of order n having partition dimension n-2. This set is formed by exactly 15 graphs, instead of 23, as was wrongly stated in the paper: "Discrepancies between metric dimension and partition dimension of a connected graph", published in Discrete Mathematics in 2008.

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.