BZPEER

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$ .

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.

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.

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.

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 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

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.

Dorota Kuziak

Research overview

Is this your work?

12 publications

Further contributions on the outer multiset dimension of graphs

Dominating the direct product of two graphs through total Roman strategies

Mixed metric dimension of graphs

On the strong metric dimension of Cartesian sum graphs

Resolvability and Strong Resolvability in the Direct Product of Graphs

Closed formulae for the strong metric dimension of lexicographic product graphs

Domination related parameters in rooted product 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

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

See the researcher in context

Building this map preview