BZPEER

preprint2024arXiv

Mutual-visibility problems on graphs of diameter two

The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$ -path $P$ so that all internal vertices of $P$ are not in $S$ . This is also said as $x,y$ are visible with respect to $S$ , or $S$ -visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside $S$ . Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters. The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankievicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Turán problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.

preprint2022arXiv

Further contributions on the outer multiset dimension of graphs

The outer multiset dimension ${\rm dim}_{\rm ms}(G)$ of a graph $G$ is the cardinality of a smallest set of vertices that uniquely recognize all the vertices outside this set by using multisets of distances to the set. It is proved that ${\rm dim}_{\rm ms}(G) = n(G) - 1$ if and only if $G$ is a regular graph with diameter at most $2$ . Graphs $G$ with ${\rm dim}_{\rm ms}(G)=2$ are described and recognized in polynomial time. A lower bound on the lexicographic product of $G$ and $H$ is proved when $H$ is complete or edgeless, and the extremal graphs are determined. It is proved that ${\rm dim}_{\rm ms}(P_s\,\square\, P_t) = 3$ for $s\ge t\ge 2$ .

preprint2021arXiv

A note on the metric and edge metric dimensions of 2-connected graphs

For a given graph $G$ , the metric and edge metric dimensions of $G$ , $\dim(G)$ and ${\rm edim}(G)$ , are the cardinalities of the smallest possible subsets of vertices in $V(G)$ such that they uniquely identify the vertices and the edges of $G$ , respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph $G$ such that $\dim(G)=a$ and ${\rm edim}(G)=b$ for every pair of integers $a,b$ , where $4\le b<a$ . For this we use subdivisions of complete graphs, whose metric dimension is in some cases smaller than the edge metric dimension. Along the way, we present an upper bound for the metric and edge metric dimensions of subdivision graphs under some special conditions.

preprint2021arXiv

On Metric Dimensions of Hypercubes

The metric (resp. edge metric or mixed metric) dimension of a graph $G$ , is the cardinality of the smallest ordered set of vertices that uniquely recognizes all the pairs of distinct vertices (resp. edges, or vertices and edges) of $G$ by using a vector of distances to this set. In this note we show two unexpected results on hypercube graphs. First, we show that the metric and edge metric dimension of $Q_d$ differ by only one for every integer $d$ . In particular, if $d$ is odd, then the metric and edge metric dimensions of $Q_d$ are equal. Second, we prove that the metric and mixed metric dimensions of the hypercube $Q_d$ are equal for every $d \ge 3$ . We conclude the paper by conjecturing that all these three types of metric dimensions of $Q_d$ are equal when $d$ is large enough.

preprint2021arXiv

Total Roman 2-domination in graphs

Given a graph $G=(V,E)$ , a function $f:V\rightarrow \{0,1,2\}$ is a total Roman $\{2\}$ -dominating function if: (1) every vertex $v\in V$ for which $f(v)=0$ satisfies that $\sum_{u\in N(v)}f(u)\geq 2$ , where $N(v)$ represents the open neighborhood of $v$ , and (2) every vertex $x\in V$ for which $f(x)\geq 1$ is adjacent to at least one vertex $y\in V$ such that $f(y)\geq 1$ . The weight of the function $f$ is defined as $ω(f)=\sum_{v\in V}f(v)$ . The total Roman $\{2\}$ -domination number, denoted by $γ_{t\{R2\}}(G)$ , is the minimum weight among all total Roman $\{2\}$ -dominating functions on $G$ . In this article we introduce the concepts above and begin the study of its combinatorial and computational properties. For instance, we give several closed relationships between this parameter and other domination related parameters in graphs. In addition, we prove that the complexity of computing the value $γ_{t\{R2\}}(G)$ is NP-hard, even when restricted to bipartite or chordal graphs.

preprint2020arXiv

A note on total co-independent domination in trees

A set $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $D$ . The total domination number of $G$ is the minimum cardinality of any total dominating set of $G$ and is denoted by $γ_t(G)$ . The total dominating set $D$ is called a total co-independent dominating set if $V(G)\setminus D$ is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by $γ_{t,coi}(G)$ . In this paper, we show that, for any tree $T$ of order $n$ and diameter at least three, $n-β(T)\leq γ_{t,coi}(T)\leq n-|L(T)|$ where $β(T)$ is the maximum cardinality of any independent set and $L(T)$ is the set of leaves of $T$ . We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of $γ_{t,coi}(T)$ and these bounds can be arbitrarily large for some classes of trees.

preprint2020arXiv

Dominating the direct product of two graphs through total Roman strategies

Given a graph $G$ without isolated vertices, a total Roman dominating function for $G$ is a function $f : V(G)\rightarrow \{0,1,2\}$ such that every vertex with label 0 is adjacent to a vertex with label 2, and the set of vertices with positive labels induces a graph of minimum degree at least one. The total Roman domination number $γ_{tR}(G)$ of $G$ is the smallest possible value of $\sum_{v\in V(G)}f(v)$ among all total Roman dominating functions $f$ . The total Roman domination number of the direct product $G\times H$ of the graphs $G$ and $H$ is studied in this work. Specifically, several relationships, in the shape of upper and lower bounds, between $γ_{tR}(G\times H)$ and some classical domination parameters for the factors are given. Characterizations of the direct product graphs $G\times H$ achieving small values ( $\le 7$ ) for $γ_{tR}(G\times H)$ are presented, and exact values for $γ_{tR}(G\times H)$ are deduced, while considering various specific direct product classes.

preprint2020arXiv

General $d$ -position sets

The general $d$ -position number ${\rm gp}_d(G)$ of a graph $G$ is the cardinality of a largest set $S$ for which no three distinct vertices from $S$ lie on a common geodesic of length at most $d$ . This new graph parameter generalizes the well studied general position number. We first give some results concerning the monotonic behavior of ${\rm gp}_d(G)$ with respect to the suitable values of $d$ . We show that the decision problem concerning finding ${\rm gp}_d(G)$ is NP-complete for any value of $d$ . The value of ${\rm gp}_d(G)$ when $G$ is a path or a cycle is computed and a structural characterization of general $d$ -position sets is shown. Moreover, we present some relationships with other topics including strong resolving graphs and dissociation sets. We finish our exposition by proving that ${\rm gp}_d(G)$ is infinite whenever $G$ is an infinite graph and $d$ is a finite integer.

preprint2020arXiv

Graphs with the edge metric dimension smaller than the metric dimension

Given a connected graph $G$ , the metric (resp. edge metric) dimension of $G$ is the cardinality of the smallest ordered set of vertices that uniquely identifies every pair of distinct vertices (resp. edges) of $G$ by means of distance vectors to such a set. In this work, we settle three open problems on (edge) metric dimension of graphs. Specifically, we show that for every $r,t\ge 2$ with $r\ne t$ , there is $n_0$ , such that for every $n\ge n_0$ there exists a graph $G$ of order $n$ with metric dimension $r$ and edge metric dimension $t$ , which among other consequences, shows the existence of infinitely many graph whose edge metric dimension is strictly smaller than its metric dimension. In addition, we also prove that it is not possible to bound the edge metric dimension of a graph $G$ by some constant factor of the metric dimension of $G$ .

preprint2020arXiv

Maker-Breaker resolving game

A set of vertices $W$ of a graph $G$ is a resolving set if every vertex of $G$ is uniquely determined by its vector of distances to $W$ . In this paper, the Maker-Breaker resolving game is introduced. The game is played on a graph $G$ by Resolver and Spoiler who alternately select a vertex of $G$ not yet chosen. Resolver wins if at some point the vertices chosen by him form a resolving set of $G$ , whereas Spoiler wins if the Resolver cannot form a resolving set of $G$ . The outcome of the game is denoted by $o(G)$ and $R_{\rm MB}(G)$ (resp. $S_{\rm MB}(G)$ ) denotes the minimum number of moves of Resolver (resp. Spoiler) to win when Resolver has the first move. The corresponding invariants for the game when Spoiler has the first move are denoted by $R'_{\rm MB}(G)$ and $S'_{\rm MB}(G)$ . Invariants $R_{\rm MB}(G)$ , $R'_{\rm MB}(G)$ , $S_{\rm MB}(G)$ , and $S'_{\rm MB}(G)$ are compared among themselves and with the metric dimension ${\rm dim}(G)$ . A large class of graphs $G$ is constructed for which $R_{\rm MB}(G) > {\rm dim}(G)$ holds. The effect of twin equivalence classes and pairing resolving sets on the Maker-Breaker resolving game is described. As an application $o(G)$ , as well as $R_{\rm MB}(G)$ and $R'_{\rm MB}(G)$ (or $S_{\rm MB}(G)$ and $S'_{\rm MB}(G)$ ), are determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.

preprint2018arXiv

The fractional $k$ -metric dimension of graphs

Let $G$ be a graph with vertex set $V(G)$ . For any two distinct vertices $x$ and $y$ of $G$ , let $R\{x, y\}$ denote the set of vertices $z$ such that the distance from $x$ to $z$ is not equal to the distance from $y$ to $z$ in $G$ . For a function $g$ defined on $V(G)$ and for $U \subseteq V(G)$ , let $g(U)=\sum_{s \in U}g(s)$ . Let $κ(G)=\min\{|R\{x,y\}|: x\neq y \mbox{ and } x,y \in V(G)\}$. For any real number $k \in [1, κ(G)]$ , a real-valued function $g: V(G) \rightarrow [0,1]$ is a \emph{ $k$ -resolving function} of $G$ if $g(R\{x,y\}) \ge k$ for any two distinct vertices $x,y \in V(G)$ . The \emph{fractional $k$ -metric dimension}, $\dim^k_f(G)$ , of $G$ is $\min\{g(V(G)): g \mbox{ is a $k$-resolving function of } G\}$. In this paper, we initiate the study of the fractional $k$ -metric dimension of graphs. For a connected graph $G$ and $k \in [1, κ(G)]$ , it's easy to see that $k \le \dim_f^k(G) \le \frac{k|V(G)|}{κ(G)}$ ; we characterize graphs $G$ satisfying $\dim_f^k(G)=k$ and $\dim_f^k(G)=|V(G)|$ , respectively. We show that $\dim_f^k(G) \ge k \dim_f(G)$ for any $k \in [1, κ(G)]$ , and we give an example showing that $\dim_f^k(G)-k\dim_f(G)$ can be arbitrarily large for some $k \in (1, κ(G)]$ ; we also describe a condition for which $\dim_f^k(G)=k\dim_f(G)$ holds. We determine the fractional $k$ -metric dimension for some classes of graphs, and conclude with two open problems, including whether $ϕ(k)=\dim_f^k(G)$ is a continuous function of $k$ on every connected graph $G$ .

preprint2016arXiv

Mixed metric dimension of graphs

Let $G=(V,E)$ be a connected graph. A vertex $w\in V$ distinguishes two elements (vertices or edges) $x,y\in E\cup V$ if $d_G(w,x)\ne d_G(w,y)$ . A set $S$ of vertices in a connected graph $G$ is a mixed metric generator for $G$ if every two elements (vertices or edges) of $G$ are distinguished by some vertex of $S$ . The smallest cardinality of a mixed metric generator for $G$ is called the mixed metric dimension and is denoted by $\mathrm{mdim}(G)$ . In this paper we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results about the mixed metric dimension of some families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.

preprint2016arXiv

On the Computational Complexities of Three Privacy Measures for Large Networks Under Active Attack

With the arrival of modern internet era, large public networks of various types have come to existence to benefit the society as a whole and several research areas such as sociology, economics and geography in particular. However, the societal and research benefits of these networks have also given rise to potentially significant privacy issues in the sense that malicious entities may violate the privacy of the users of such a network by analyzing the network and deliberately using such privacy violations for deleterious purposes. Such considerations have given rise to a new active research area that deals with the quantification of privacy of users in large networks and the corresponding investigation of computational complexity issues of computing such quantified privacy measures. In this paper, we formalize three such privacy measures for large networks and provide non-trivial theoretical computational complexity results for computing these measures. Our results show the first two measures can be computed efficiently, whereas the third measure is provably hard to compute within a logarithmic approximation factor. Furthermore, we also provide computational complexity results for the case when the privacy requirement of the network is severely restricted, including an efficient logarithmic approximation.

preprint2016arXiv

The fractional strong metric dimension in three graph products

For any two distinct vertices $x$ and $y$ of a graph $G$ , let $S\{x, y\}$ denote the set of vertices $z$ such that either $x$ lies on a $y-z$ geodesic or $y$ lies on an $x-z$ geodesic. Let $g: V(G) \rightarrow [0,1]$ be a real valued function and, for any $U \subseteq V(G)$ , let $g(U)=\sum_{v \in U}g(v)$ . The function $g$ is a strong resolving function of $G$ if $g(S\{x, y\}) \ge 1$ for every pair of distinct vertices $x, y$ of $G$ . The fractional strong metric dimension, $sdim_f(G)$ , of a graph $G$ is $\min\{g(V(G)): g \mbox{ is a strong resolving function of }G\}$. In this paper, after obtaining some new results for all connected graphs, we focus on the study of the fractional strong metric dimension of the corona product, the lexicographic product, and the Cartesian product of graphs.

preprint2016arXiv

Uniquely identifying the edges of a graph: the edge metric dimension

Let $G=(V,E)$ be a connected graph, let $v\in V$ be a vertex and let $e=uw\in E$ be an edge. The distance between the vertex $v$ and the edge $e$ is given by $d_G(e,v)=\min\{d_G(u,v),d_G(w,v)\}$ . A vertex $w\in V$ distinguishes two edges $e_1,e_2\in E$ if $d_G(w,e_1)\ne d_G(w,e_2)$ . A set $S$ of vertices in a connected graph $G$ is an edge metric generator for $G$ if every two edges of $G$ are distinguished by some vertex of $S$ . The smallest cardinality of an edge metric generator for $G$ is called the edge metric dimension and is denoted by $edim(G)$ . In this article we introduce the concept of edge metric dimension and initiate the study of its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the edge metric dimension and the standard metric dimension of graphs. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present some bounds and closed formulae for the edge metric dimension of several classes of graphs.

preprint2015arXiv

Graphs that are simultaneously efficient open domination and efficient closed domination graphs

A graph is an efficient open (resp.\ closed) domination graph if there exists a subset of vertices whose open (resp.\ closed) neighborhoods partition its vertex set. Graphs that are efficient open as well as efficient closed (shortly EOCD graphs) are investigated. The structure of EOCD graphs with respect to their efficient open and efficient closed dominating sets is explained. It is shown that the decision problem regarding whether a graph is an EOCD graph is an NP-complete problem. A recursive description that constructs all EOCD trees is given and EOCD graphs are characterized among the Sierpiński graphs.

preprint2015arXiv

k-Metric Antidimension: a Privacy Measure for Social Graphs

Let $G = (V, E)$ be a simple connected graph and $S = \{w_1, \cdots, w_t\} \subseteq V$ an ordered subset of vertices. The metric representation of a vertex $u\in V$ with respect to $S$ is the $t$ -vector $r(u|S) = (d_G(u, w_1), \cdots, d_G(u, w_t))$ , where $d_G(u, v)$ represents the length of a shortest $u-v$ path in $G$ . The set $S$ is called a resolving set for $G$ if $r(u|S) = r(v|S)$ implies $u = v$ for every $u, v \in V$ . The smallest cardinality of a resolving set is the metric dimension of $G$ . In this article we propose, to the best of our knowledge, a new problem in Graph Theory that resembles to the aforementioned metric dimension problem. We call $S$ a $k$ -antiresolving set if $k$ is the largest positive integer such that for every vertex $v \in V-S$ there exist other $k-1$ different vertices $v_1, \cdots, v_{k-1} \in V-S$ with $r(v|S) = r(v_1|S) = \cdots = r(v_{k-1}|S)$ , \emph{i.e.}, $v$ and $v_1, \cdots, v_{k-1}$ have the same metric representation with respect to $S$ . The $k$ -metric antidimension of $G$ is the minimum cardinality among all the $k$ -antiresolving sets for $G$ . In this article, we introduce a novel privacy measure, named $(k, \ell)$ -anonymity and based on the $k$ -metric antidimension problem, aimed at evaluating the resistance of social graphs to active attacks. We, therefore, propose a true-biased algorithm for computing the $k$ -metric antidimension of random graphs. The success rate of our algorithm, according to empirical results, is above $80 \%$ and $90 \%$ when looking for a $k$ -antiresolving basis and a $k$ -antiresolving set respectively. We also investigate theoretical properties of the $k$ -antiresolving sets and the $k$ -metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees.

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

On the strong metric dimension of Cartesian sum graphs

A vertex $w$ of a connected graph $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 tight bounds or closed formulae for the strong metric dimension of the Cartesian sum of graphs in terms of the strong metric dimension, clique number or twins-free clique number of its factor graphs.

preprint2015arXiv

Resolvability and Strong Resolvability in the Direct Product of Graphs

Given a connected graph $G$ , a vertex $w\in V(G)$ distinguishes two different vertices $u,v$ of $G$ if the distances between $w$ and $u$ and between $w$ and $v$ are different. Moreover, $w$ strongly resolves the pair $u,v$ 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) metric generator for $G$ if every pair of vertices of $G$ is (strongly resolved) distinguished by some vertex of $W$ . The smallest cardinality of a (strong) metric generator for $G$ is called the (strong) metric dimension of $G$ . In this article we study the (strong) metric dimension of some families of direct product graphs.

preprint2015arXiv

The k-metric dimension of a graph

As a generalization of the concept of a metric basis, this article introduces the notion of $k$ -metric basis in graphs. Given a connected graph $G=(V,E)$ , a set $S\subseteq V$ is said to be a $k$ -metric generator for $G$ if the elements of any pair of different vertices of $G$ are distinguished by at least $k$ elements of $S$ , i.e., for any two different vertices $u,v\in V$ , there exist at least $k$ vertices $w_1,w_2,...,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$ . A connected graph $G$ is $k$ -metric dimensional if $k$ is the largest integer such that there exists a $k$ -metric basis for $G$ . We give a necessary and sufficient condition for a graph to be $k$ -metric dimensional and we obtain several results on the $k$ -metric dimension.

preprint2014arXiv

Bondage number of grid graphs

The bondage number $b(G)$ of a nonempty graph $G$ is the cardinality of a smallest set of edges whose removal from $G$ results in a graph with domination number greater than the domination number of $G$ . Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

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

Domination related parameters in rooted product graphs

A set $S$ of vertices of a graph $G$ is a dominating set in $G$ if every vertex outside of $S$ is adjacent to at least one vertex belonging to $S$ . A domination parameter of $G$ is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of $G$ . Here, we investigate several domination related parameters in rooted product graphs.

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

On the strong metric dimension of Cartesian and direct products of graphs

Let $G$ be a connected graph. A vertex $w$ {\em 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 {\em 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 {\em strong metric dimension} of $G$ . It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian product graphs and direct product graphs.

preprint2013arXiv

On the strong metric generators of strong product graphs

Let $G$ be a connected graph. 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$ . It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.

preprint2013arXiv

Strong metric dimension of rooted product 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. This suggests finding the strong metric dimension for special classes of graphs or obtaining good bounds on this invariant. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of rooted product of graphs and express these in terms of invariants of the factor graphs.

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

Computing global offensive alliances in Cartesian product graphs

A global offensive alliance in a graph $G$ is a set $S$ of vertices with the property that every vertex not belonging to $S$ has at least one more neighbor in $S$ than it has outside of $S$ . The global offensive alliance number of $G$ , $γ_o(G)$ , is the minimum cardinality of a global offensive alliance in $G$ . A set $S$ of vertices of a graph $G$ is a dominating set for $G$ if every vertex not belonging to $S$ has at least one neighbor in $S$ . The domination number of $G$ , $γ(G)$ , is the minimum cardinality of a dominating set of $G$ . In this work we obtain closed formulas for the global offensive alliance number of several families of Cartesian product graphs, we also prove that $γ_o(G\square H)\ge \frac{γ(G)γ_o(H)}{2}$ for any graphs $G$ and $H$ and we show that if $G$ has an efficient dominating set, then $γ_o(G\square H)\ge γ(G)γ_o(H).$ Moreover, we present a Vizing-like conjecture for the global offensive alliance number and we prove it for several families of graphs.

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

A note on the partition dimension of Cartesian product graphs

Let $G=(V,E)$ be a connected graph. The distance between two vertices $u,v\in V$ , denoted by $d(u, v)$ , is the length of a shortest $u-v$ path in $G$ . The distance between a vertex $v\in V$ and a subset $P\subset V$ is defined as $min\{d(v, x): x \in P\}$ , and it is denoted by $d(v, P)$ . An ordered partition $\{P_1,P_2, ...,P_t\}$ of vertices of a graph $G$ , is a \emph{resolving partition}of $G$ , if all the distance vectors $(d(v,P_1),d(v,P_2),...,d(v,P_t))$ are different. The \emph{partition dimension} of $G$ , denoted by $pd(G)$ , is the minimum number of sets in any resolving partition of $G$ . In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs $G, H$ , $pd(G\times H)\le pd(G)+pd(H)$ and $pd(G\times H)\le pd(G)+dim(H).$ Consequently, we show that $pd(G\times H)\le dim(G)+dim(H)+1.$

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.

Ismael G. Yero

Research overview

Is this your work?

38 publications

Mutual-visibility problems on graphs of diameter two

Further contributions on the outer multiset dimension of graphs

A note on the metric and edge metric dimensions of 2-connected graphs

On Metric Dimensions of Hypercubes

Total Roman 2-domination in graphs

A note on total co-independent domination in trees

Dominating the direct product of two graphs through total Roman strategies

General ddd-position sets

Graphs with the edge metric dimension smaller than the metric dimension

Maker-Breaker resolving game

The fractional kkk-metric dimension of graphs

Mixed metric dimension of graphs

On the Computational Complexities of Three Privacy Measures for Large Networks Under Active Attack

The fractional strong metric dimension in three graph products

Uniquely identifying the edges of a graph: the edge metric dimension

Graphs that are simultaneously efficient open domination and efficient closed domination graphs

k-Metric Antidimension: a Privacy Measure for Social Graphs

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

On the strong metric dimension of Cartesian sum graphs

Resolvability and Strong Resolvability in the Direct Product of Graphs

The k-metric dimension of a graph

Bondage number of grid graphs

Closed formulae for the strong metric dimension of lexicographic product graphs

Domination related parameters in rooted product graphs

On the partition dimension of unicyclic graphs

On the strong metric dimension of Cartesian and direct products of graphs

On the strong metric generators of strong product graphs

Strong metric dimension of rooted product graphs

The metric dimension of strong product graphs

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

Computing global offensive alliances in Cartesian product 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

A note on the partition dimension of Cartesian 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

General $d$ -position sets

The fractional $k$ -metric dimension of graphs

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