Source author record

Juan A. Rodriguez-Velazquez

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

17works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On distances in generalized Sierpinski graphs

In this paper we propose formulas for the distance between vertices of a generalized Sierpiński graph $S(G,t)$ in terms of the distance between vertices of the base graph $G$ . In particular, we deduce a recursive formula for the distance between an arbitrary vertex and an extreme vertex of $S(G,t)$ , and we obtain a recursive formula for the distance between two arbitrary vertices of $S(G,t)$ when the base graph is triangle-free. From these recursive formulas, we provide algorithms to compute the distance between vertices of $S(G,t)$ . In addition, we give an explicit formula for the diameter and radius of $S(G,t)$ when the base graph is a tree.

preprint2016arXiv

On the local metric dimension of corona product graphs

A vertex $v\in V(G)$ is said to distinguish two vertices $x,y\in V(G)$ of a nontrivial connected graph $G$ if the distance from $v$ to $x$ is different from the distance from $v$ to $y$ . A set $S\subset V(G)$ is a local metric generator for $G$ if every two adjacent vertices of $G$ are distinguished by some vertex in $S$ . A local metric generator with the minimum cardinality is called a local metric basis for $G$ and its cardinality, the local metric dimension of G. In this paper we study the problem of finding exact values for the local metric dimension of corona product of graphs.

preprint2016arXiv

On the Roman domination number of generalized Sierpinski graphs

A map $f : V \rightarrow \{0, 1, 2\}$ is a Roman dominating function on a graph $G=(V,E)$ if for every vertex $v\in V$ with $f(v) = 0$ , there exists a vertex $u$ , adjacent to $v$ , such that $f(u) = 2$ . The weight of a Roman dominating function is given by $f(V) =\sum_{u\in V}f(u)$ . The minimum weight of a Roman dominating function on $G$ is called the Roman domination number of $G$ . In this article we study the Roman domination number of Generalized Sierpiński graphs $S(G,t)$ . More precisely, we obtain a general upper bound on the Roman domination number of $S(G,t)$ and we discuss the tightness of this bound. In particular, we focus on the cases in which the base graph $G$ is a path, a cycle, a complete graph or a graph having exactly one universal vertex.

preprint2015arXiv

On the complexity of computing the $k$ -metric dimension of graphs

Given a connected graph $G=(V,E)$ , a set $S\subseteq V$ is a $k$ -metric generator for $G$ if for any two different vertices $u,v\in V$ , there exist at least $k$ vertices $w_1,...,w_k\in S$ such that $d_G(u,w_i)\ne d_G(v,w_i)$ for every $i\in \{1,...,k\}$ . A metric generator of minimum cardinality is called a $k$ -metric basis and its cardinality the $k$ -metric dimension of $G$ . We study some problems regarding the complexity of some $k$ -metric dimension problems. For instance, we show that the problem of computing the $k$ -metric dimension of graphs is $NP$ -Complete. However, the problem is solved in linear time for the particular case of trees.

preprint2015arXiv

The local metric dimension of strong product graphs

A vertex $v\in V(G)$ is said to distinguish two vertices $x,y\in V(G)$ of a nontrivial connected graph $G$ if the distance from $v$ to $x$ is different from the distance from $v$ to $y$ . A set $S\subset V(G)$ is a local metric generator for $G$ if every two adjacent vertices of $G$ are distinguished by some vertex of $S$ . A local metric generator with the minimum cardinality is called a local metric basis for $G$ and its cardinality, the local metric dimension of $G$ . It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.

preprint2014arXiv

Closed formulae for the strong metric dimension of lexicographic product graphs

Given a connected graph $G$ , a vertex $w\in V(G)$ strongly resolves two vertices $u,v\in V(G)$ if there exists some shortest $u-w$ path containing $v$ or some shortest $v-w$ path containing $u$ . A set $S$ of vertices is a strong metric generator for $G$ if every pair of vertices of $G$ is strongly resolved by some vertex of $S$ . The smallest cardinality of a strong metric generator for $G$ is called the strong metric dimension of $G$ . In this paper we obtain several relationships between the strong metric dimension of the lexicographic product of graphs and the strong metric dimension of its factor graphs.

preprint2013arXiv

Alliances and related parameters in graphs

In this paper, we show that several graph parameters are known in different areas under completely different names. More specifically, our observations connect signed domination, monopolies, $α$ -domination, $α$ -independence, positive influence domination, and a parameter associated to fast information propagation in networks to parameters related to various notions of global $r$ -alliances in graphs. We also propose a new framework, called (global) $(D,O)$ -alliances, not only in order to characterize various known variants of alliance and domination parameters, but also to suggest a unifying framework for the study of alliances and domination. Finally, we also give a survey on the mentioned graph parameters, indicating how results transfer due to our observations.

preprint2013arXiv

On the partition dimension of unicyclic graphs

Given an ordered partition $Π=\{P_1,P_2, ...,P_t\}$ of the vertex set $V$ of a connected graph $G=(V,E)$ , the \emph{partition representation} of a vertex $v\in V$ with respect to the partition $Π$ is the vector $r(v|Π)=(d(v,P_1),d(v,P_2),...,d(v,P_t))$ , where $d(v,P_i)$ represents the distance between the vertex $v$ and the set $P_i$ . A partition $Π$ of $V$ is a \emph{resolving partition} if different vertices of $G$ have different partition representations, i.e., for every pair of vertices $u,v\in V$ , $r(u|Π)\ne r(v|Π)$ . The \emph{partition dimension} of $G$ is the minimum number of sets in any resolving partition for $G$ . In this paper we obtain several tight bounds on the partition dimension of unicyclic graphs.

preprint2013arXiv

The Hosoya polynomial of distance-regular graphs

In this note we obtain an explicit formula for the Hosoya polynomial of any distance-regular graph in terms of its intersection array. As a consequence, we obtain a very simple formula for the Hosoya polynomial of any strongly regular graph.

preprint2013arXiv

The metric dimension of strong product graphs

For an ordered subset $S = \{s_1, s_2,\dots s_k\}$ of vertices and a vertex $u$ in a connected graph $G$ , the metric representation of $u$ with respect to $S$ is the ordered $k$ -tuple $r(u|S)=(d_G(v,s_1), d_G(v,s_2),\dots,$ $d_G(v,s_k))$ , where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$ . The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$ , the metric dimension of $G$ . It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.

preprint2012arXiv

Analogies between the geodetic number and the Steiner number of some classes of graphs

A set of vertices $S$ of a graph $G$ is a geodetic set of $G$ if every vertex $v\not\in S$ lies on a shortest path between two vertices of $S$ . The minimum cardinality of a geodetic set of $G$ is the geodetic number of $G$ and it is denoted by $g(G)$ . A Steiner set of $G$ is a set of vertices $W$ of $G$ such that every vertex of $G$ belongs to the set of vertices of a connected subgraph of minimum size containing the vertices of $W$ . The minimum cardinality of a Steiner set of $G$ is the Steiner number of $G$ and it is denoted by $s(G)$ . Let $G$ and $H$ be two graphs and let $n$ be the order of $G$ . The corona product $G\odot H$ is defined as the graph obtained from $G$ and $H$ by taking one copy of $G$ and $n$ copies of $H$ and joining by an edge each vertex from the $i^{th}$ -copy of $H$ with the $i^{th}$ -vertex of $G$ . We study the geodetic number and the Steiner number of corona product graphs. We show that if $G$ is a connected graph of order $n\ge 2$ and $H$ is a non complete graph, then $g(G\odot H)\le s(G\odot H)$ , which partially solve the open problem presented in [\emph{Discrete Mathematics} \textbf{280} (2004) 259--263] related to characterize families of graphs $G$ satisfying that $g(G)\le s(G)$ .

preprint2012arXiv

On the strong metric dimension of corona product graphs and join graphs

Let $G$ be a connected graph. A vertex $w$ strongly resolves a pair $u$ , $v$ of vertices of $G$ if there exists some shortest $u-w$ path containing $v$ or some shortest $v-w$ path containing $u$ . A set $W$ of vertices is a strong resolving set for $G$ if every pair of vertices of $G$ is strongly resolved by some vertex of $W$ . The smallest cardinality of a strong resolving set for $G$ is called the strong metric dimension of $G$ . It is known that the problem of computing this invariant is NP-hard. It is therefore desirable to reduce the problem of computing the strong metric dimension of product graphs, to the problem of computing some parameter of the factor graphs. We show that the problem of finding the strong metric dimension of the corona product $G\odot H$ , of two graphs $G$ and $H$ , can be transformed to the problem of finding certain clique number of $H$ . As a consequence of the study we show that if $H$ has diameter two, then the strong metric dimension of $G\odot H$ is obtained from the strong metric dimension of $H$ and, if $H$ is not connected or its diameter is greater than two, then the strong metric dimension of $G\odot H$ is obtained from the strong metric dimension of $K_1\odot H$ , where $K_1$ denotes the trivial graph. The strong metric dimension of join graphs is also studied.

preprint2011arXiv

Alliance free sets in Cartesian product graphs

Let $G=(V,E)$ be a graph. For a non-empty subset of vertices $S\subseteq V$ , and vertex $v\in V$ , let $δ_S(v)=|\{u\in S:uv\in E\}|$ denote the cardinality of the set of neighbors of $v$ in $S$ , and let $\bar{S}=V-S$ . Consider the following condition: {equation}\label{alliancecondition} δ_S(v)\ge δ_{\bar{S}}(v)+k, \{equation} which states that a vertex $v$ has at least $k$ more neighbors in $S$ than it has in $\bar{S}$ . A set $S\subseteq V$ that satisfies Condition (\ref{alliancecondition}) for every vertex $v \in S$ is called a \emph{defensive} $k$ -\emph{alliance}; for every vertex $v$ in the neighborhood of $S$ is called an \emph{offensive} $k$ -\emph{alliance}. A subset of vertices $S\subseteq V$ , is a \emph{powerful} $k$ -\emph{alliance} if it is both a defensive $k$ -alliance and an offensive $(k +2)$ -alliance. Moreover, a subset $X\subset V$ is a defensive (an offensive or a powerful) $k$ -alliance free set if $X$ does not contain any defensive (offensive or powerful, respectively) $k$ -alliance. In this article we study the relationships between defensive (offensive, powerful) $k$ -alliance free sets in Cartesian product graphs and defensive (offensive, powerful) $k$ -alliance free sets in the factor graphs.

preprint2011arXiv

On the partition dimension of trees

Given an ordered partition $Π=\{P_1,P_2, ...,P_t\}$ of the vertex set $V$ of a connected graph $G=(V,E)$ , the \emph{partition representation} of a vertex $v\in V$ with respect to the partition $Π$ is the vector $r(v|Π)=(d(v,P_1),d(v,P_2),...,d(v,P_t))$ , where $d(v,P_i)$ represents the distance between the vertex $v$ and the set $P_i$ . A partition $Π$ of $V$ is a \emph{resolving partition} of $G$ if different vertices of $G$ have different partition representations, i.e., for every pair of vertices $u,v\in V$ , $r(u|Π)\ne r(v|Π)$ . The \emph{partition dimension} of $G$ is the minimum number of sets in any resolving partition of $G$ . In this paper we obtain several tight bounds on the partition dimension of trees.

preprint2011arXiv

Roman domination in Cartesian product graphs and strong product graphs

A set $S$ of vertices of a graph $G$ is a dominating set for $G$ if every vertex outside of $S$ is adjacent to at least one vertex belonging to $S$ . The minimum cardinality of a dominating set for $G$ is called the domination number of $G$ . A map $f : V \rightarrow \{0, 1, 2\}$ is a Roman dominating function on a graph $G$ if for every vertex $v$ with $f(v) = 0$ , there exists a vertex $u$ , adjacent to $v$ , such that $f(u) = 2$ . The weight of a Roman dominating function is given by $f(V) =\sum_{u\in V}f(u)$ . The minimum weight of a Roman dominating function on $G$ is called the Roman domination number of $G$ . In this article we study the Roman domination number of Cartesian product graphs and strong product graphs. More precisely, we study the relationships between the Roman domination number of product graphs and the (Roman) domination number of the factors.

preprint2010arXiv

Partitioning a graph into defensive k-alliances

A defensive $k$ -alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$ . A defensive $k$ -alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$ -alliances. The (global) defensive $k$ -alliance partition number of a graph $Γ=(V,E)$ , ( $ψ_{k}^{gd}(Γ)$ ) $ψ_k^{d}(Γ)$ , is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$ -alliance. We obtain tight bounds on $ψ_k^{d}(Γ)$ and $ψ_{k}^{gd}(Γ)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Γ_1\times Γ_2$ into (global) defensive $(k_1+k_2)$ -alliances and partitions of $Γ_i$ into (global) defensive $k_i$ -alliances, $i\in \{1,2\}$ .

preprint2009arXiv

On global offensive k-alliances in graphs

We investigate the relationship between global offensive $k$ -alliances and some characteristic sets of a graph including $r$ -dependent sets and $τ$ -dominating sets. As a consequence of the study, we obtain bounds on the global offensive $k$ -alliance number in terms of several parameters of the graph.

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.

Juan A. Rodriguez-Velazquez

Research overview

Is this your work?

17 publications

On distances in generalized Sierpinski graphs

On the local metric dimension of corona product graphs

On the Roman domination number of generalized Sierpinski graphs

On the complexity of computing the $k$ -metric dimension of graphs

The local metric dimension of strong product graphs

Closed formulae for the strong metric dimension of lexicographic product graphs

Alliances and related parameters in graphs

On the partition dimension of unicyclic graphs

The Hosoya polynomial of distance-regular graphs

The metric dimension of strong product graphs

Analogies between the geodetic number and the Steiner number of some classes of graphs

On the strong metric dimension of corona product graphs and join graphs

Alliance free sets in Cartesian product graphs

On the partition dimension of trees

Roman domination in Cartesian product graphs and strong product graphs

Partitioning a graph into defensive k-alliances

On global offensive k-alliances in graphs

See the researcher in context

Building this map preview

Juan A. Rodriguez-Velazquez

Research overview

Is this your work?

17 publications

On distances in generalized Sierpinski graphs

On the local metric dimension of corona product graphs

On the Roman domination number of generalized Sierpinski graphs

On the complexity of computing the kkk-metric dimension of graphs

The local metric dimension of strong product graphs

Closed formulae for the strong metric dimension of lexicographic product graphs

Alliances and related parameters in graphs

On the partition dimension of unicyclic graphs

The Hosoya polynomial of distance-regular graphs

The metric dimension of strong product graphs

Analogies between the geodetic number and the Steiner number of some classes of graphs

On the strong metric dimension of corona product graphs and join graphs

Alliance free sets in Cartesian product graphs

On the partition dimension of trees

Roman domination in Cartesian product graphs and strong product graphs

Partitioning a graph into defensive k-alliances

On global offensive k-alliances in graphs

See the researcher in context

Building this map preview

On the complexity of computing the $k$ -metric dimension of graphs