BZPEER

preprint2022arXiv

Distance- $k$ locating-dominating sets in graphs

Let $G$ be a graph with vertex set $V$ , and let $k$ be a positive integer. A set $D \subseteq V$ is a \emph{distance- $k$ dominating set} of $G$ if, for each vertex $u \in V-D$ , there exists a vertex $w\in D$ such that $d(u,w) \le k$ , where $d(u,w)$ is the minimum number of edges linking $u$ and $w$ in $G$ . Let $d_k(x, y)=\min\{d(x,y), k+1\}$ . A set $R\subseteq V$ is a \emph{distance- $k$ resolving set} of $G$ if, for any pair of distinct $x,y\in V$ , there exists a vertex $z\in R$ such that $d_k(x,z) \neq d_k(y,z)$ . The \emph{distance- $k$ domination number} $γ_k(G)$ (\emph{distance- $k$ dimension} $\dim_k(G)$ , respectively) of $G$ is the minimum cardinality of all distance- $k$ dominating sets (distance- $k$ resolving sets, respectively) of $G$ . The \emph{distance- $k$ location-domination number}, $γ_L^k(G)$ , of $G$ is the minimum cardinality of all sets $S\subseteq V$ such that $S$ is both a distance- $k$ dominating set and a distance- $k$ resolving set of $G$ . Note that $γ_L^1(G)$ is the well-known location-domination number introduced by Slater in 1988. For any connected graph $G$ of order $n\ge 2$ , we obtain the following sharp bounds: (1) $γ_k(G) \le \dim_k(G)+1$ ; (2) $2\leγ_k(G)+\dim_k(G) \le n$ ; (3) $1\le \max\{γ_k(G), \dim_k(G)\} \le γ_L^k(G) \le \min\{\dim_k(G)+1, n-1\}$ . We characterize $G$ for which $γ_L^k(G)\in\{1, |V|-1\}$ . We observe that $\frac{\dim_k(G)}{γ_k(G)}$ can be arbitrarily large. Moreover, for any tree $T$ of order $n\ge 2$ , we show that $γ_L^k(T)\le n-ex(T)$ , where $ex(T)$ denotes the number of exterior major vertices of $T$ , and we characterize trees $T$ achieving equality. We also examine the effect of edge deletion on the distance- $k$ location-domination number of graphs.

preprint2022arXiv

Maker-Breaker Metric Resolving Games on Graphs

Let $d(x,y)$ denote the length of a shortest path between vertices $x$ and $y$ in a graph $G$ with vertex set $V$ . For a positive integer $k$ , let $d_k(x,y)=\min\{d(x,y), k+1\}$ and $R_k\{x,y\}=\{z\in V: d_k(x,z) \neq d_k(y,z)\}$ . A set $S \subseteq V$ is a \emph{distance- $k$ resolving set} of $G$ if $S \cap R_k\{x,y\} \neq\emptyset$ for distinct $x,y\in V$ . In this paper, we study the maker-breaker distance- $k$ resolving game (MB $k$ RG) played on a graph $G$ by two players, Maker and Breaker, who alternately select a vertex of $G$ not yet chosen. Maker wins by selecting vertices which form a distance- $k$ resolving set of $G$ , whereas Breaker wins by preventing Maker from winning. We denote by $O_{R,k}(G)$ the outcome of MB $k$ RG. Let $\mathcal{M}$ , $\mathcal{B}$ and $\mathcal{N}$ , respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB $k$ RG. Given a graph $G$ , the parameter $O_{R,k}(G)$ is a non-decreasing function of $k$ with codomain $\{-1=\mathcal{B}, 0=\mathcal{N}, 1=\mathcal{M}\}$ . We exhibit pairs $G$ and $k$ such that the ordered pair $(O_{R,k}(G), O_{R, k+1}(G))$ realizes each member of the set $\{(\mathcal{B}, \mathcal{N}),(\mathcal{B}, \mathcal{M}),(\mathcal{N},\mathcal{M})\}$ ; we provide graphs $G$ such that $O_{R,1}(G)=\mathcal{B}$ , $O_{R,2}(G)=\mathcal{N}$ and $O_{R,k}(G)=\mathcal{M}$ for $k\ge3$ . Moreover, we obtain some general results on MB $k$ RG and study the MB $k$ RG played on some graph classes.

preprint2022arXiv

The Simultaneous Fractional Dimension of Graph Families

A subset $S$ of the vertices $V$ of a connected graph $G$ resolves $G$ if no two vertices of $V$ share the same list of distances (shortest-path metric) with respect to the vertices of $S$ listed in a given order. The choice of such an $S$ in $V$ amounts to selecting a binary valued function $g$ , said to be a resolving function, on $V$ . The notion of a fractional resolving function is obtained by relaxing the codomain of $g$ to be the unit interval. Let $|g|=\sum_{v\in V}g(v)$ . Given a finite collection $\mathcal{G}$ of connected graphs on a common vertex set $V$ , the simultaneous metric dimension of $\mathcal{G}$ is the minimum cardinality of $|S|$ over all $S$ which resolve each member graph of $\mathcal{G}$ . In this paper, we initiate the study of simultaneous fractional dimension ${\rm Sd}_f(\mathcal{G})$ of a graph family $\mathcal{G}$ , defined to be the minimum $|g|$ over all functions $g$ each resolving all members of $\mathcal{G}$ . We characterize the lower bound and examine the upper bound satisfied by ${\rm Sd}_f(\mathcal{G})$ . We examine ${\rm Sd}_f(\mathcal{G})$ for families of vertex transitive graphs and for pairs $\{G,\overline{G}\}$ of complementary graphs, determining ${\rm Sd}_f(G,\overline{G})$ when $G$ is a tree or a unicyclic graph.

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.

preprint2020arXiv

On Laplacian Monopoles

We consider the action of the (combinatorial) Laplacian of a finite and simple graph on integer vectors. By a \emph{Laplacian monopole} we mean an image vector negative at exactly one coordinate associated with a vertex. We consider a numerical semigroup $H_f(P)$ given by all monopoles at a vertex of a graph. The well-known analogy between finite graphs and algebraic curves (Riemann surfaces) has motivated much work. More specifically for us, the motivation arises out of the classical Weierstrass semigroup of a rational point on a curve whose properties are tied to the Riemann-Roch Theorem, as well as out of the graph theoretic Riemann-Roch Theorem demonstrated by Baker and Norine. We determine $H_f(P)$ for some families of graphs and demonstrate a connection between $H_f(P)$ and the vertex (also edge) connectivity of a graph. We also study $H_r(P)$ , another numerical semigroup which arises out of the result of Baker and Norine, and explore its connection to $H_f(P)$ on graphs. We show that $H_r(P)\subseteq H_f(P)$ in a number of special cases. In contrast to the situation in the classical setting, we demonstrate that $H_f(P)\setminus H_r(P)$ can be arbitrarily large and identify a potential obstruction to the inclusion of $H_r(P)$ in $H_f(P)$ in general, though we still conjecture this inclusion. We conclude with a few open questions.

preprint2018arXiv

The connected metric dimension at a vertex of a graph

The notion of metric dimension, $dim(G)$ , of a graph $G$ , as well as a number of variants, is now well studied. In this paper, we begin a local analysis of this notion by introducing $cdim_G(v)$ , \emph{the connected metric dimension of $G$ at a vertex $v$ }, which is defined as follows: a set of vertices $S$ of $G$ is a \emph{resolving set} if, for any pair of distinct vertices $x$ and $y$ of $G$ , there is a vertex $z \in S$ such that the distance between $z$ and $x$ is distinct from the distance between $z$ and $y$ in $G$ . We call a resolving set $S$ \emph{connected} if $S$ induces a connected subgraph of $G$ . Then, $cdim_G(v)$ is defined to be the minimum of the cardinalities of all connected resolving sets which contain the vertex $v$ . The \emph{connected metric dimension of $G$ }, denoted by $cdim(G)$ , is $\min\{cdim_G(v): v \in V(G)\}$ . Noting that $1 \le dim(G) \le cdim(G) \le cdim_G(v) \le |V(G)|-1$ for any vertex $v$ of $G$ , we show the existence of a pair $(G,v)$ such that $cdim_G(v)$ takes all positive integer values from $dim(G)$ to $|V (G)|-1$ , as $v$ varies in a fixed graph $G$ . We characterize graphs $G$ and their vertices $v$ satisfying $cdim_G(v) \in \{1, |V(G)|-1\}$ . We show that $cdim(G)=2$ implies $G$ is planar, whereas it is well known that there is a non-planar graph $H$ with $dim(H)=2$ . We also characterize trees and unicyclic graphs $G$ satisfying $cdim(G)=dim(G)$ . We show that $cdim(G)-dim(G)$ can be arbitrarily large. We determine $cdim(G)$ and $cdim_G(v)$ for some classes of graphs. We further examine the effect of vertex or edge deletion on the connected metric dimension. We conclude with some open problems.

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

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.

preprint2014arXiv

A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs

The \emph{zero forcing number}, $Z(G)$ , of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G)-S$ are colored white) such that $V(G)$ is turned black after finitely many applications of "the color-change rule": a white vertex is converted black if it is the only white neighbor of a black vertex. The \emph{strong metric dimension}, $sdim(G)$ , of a graph $G$ is the minimum among cardinalities of all strong resolving sets: $W \subseteq V(G)$ is a \emph{strong resolving set} of $G$ if for any $u, v \in V(G)$ , there exists an $x \in W$ such that either $u$ lies on an $x-v$ geodesic or $v$ lies on an $x-u$ geodesic. In this paper, we prove that $Z(G) \le sdim(G)+3r(G)$ for a connected graph $G$ , where $r(G)$ is the cycle rank of $G$ . Further, we prove the sharp bound $Z(G) \leq sdim(G)$ when $G$ is a tree or a unicyclic graph, and we characterize trees $T$ attaining $Z(T)=sdim(T)$ . It is easy to see that $sdim(T+e)-sdim(T)$ can be arbitrarily large for a tree $T$ ; we prove that $sdim(T+e) \ge sdim(T)-2$ and show that the bound is sharp.

preprint2014arXiv

On Domination Number and Distance in Graphs

A vertex set $S$ of a graph $G$ is a \emph{dominating set} if each vertex of $G$ either belongs to $S$ or is adjacent to a vertex in $S$ . The \emph{domination number} $γ(G)$ of $G$ is the minimum cardinality of $S$ as $S$ varies over all dominating sets of $G$ . It is known that $γ(G) \ge \frac{1}{3}(diam(G)+1)$ , where $diam(G)$ denotes the diameter of $G$ . Define $C_r$ as the largest constant such that $γ(G) \ge C_r \sum_{1 \le i < j \le r}d(x_i, x_j)$ for any $r$ vertices of an arbitrary connected graph $G$ ; then $C_2=\frac{1}{3}$ in this view. The main result of this paper is that $C_r=\frac{1}{r(r-1)}$ for $r\geq 3$ . It immediately follows that $γ(G)\geq μ(G)=\frac{1}{n(n-1)}W(G)$ , where $μ(G)$ and $W(G)$ are respectively the average distance and the Wiener index of $G$ of order $n$ . As an application of our main result, we prove a conjecture of DeLaViña et al.\;that $γ(G)\geq \frac{1}{2}(ecc_G(B)+1)$ , where $ecc_G(B)$ denotes the eccentricity of the boundary of an arbitrary connected graph $G$ .

preprint2013arXiv

Metric Dimension and Zero Forcing Number of Two Families of Line Graphs

Zero forcing number has recently become an interesting graph parameter studied in its own right since its introduction by the "AIM Minimum Rank -- Special Graphs Work Group", whereas metric dimension is a well-known graph parameter. We investigate the metric dimension and the zero forcing number of some line graphs by first determining the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. We prove that $Z(G) \le 2Z(L(G))$ for a simple and connected graph $G$ . Further, we show that $Z(G) \le Z(L(G))$ when $G$ is a tree or when $G$ contains a Hamiltonian path and has a certain number of edges. We compare the metric dimension with the zero forcing number of a line graph by demonstrating a couple of inequalities between the two parameters. We end by stating some open problems.

preprint2012arXiv

On Metric Dimension of Functigraphs

The \emph{metric dimension} of a graph $G$ , denoted by $\dim(G)$ , is the minimum number of vertices such that each vertex is uniquely determined by its distances to the chosen vertices. Let $G_1$ and $G_2$ be disjoint copies of a graph $G$ and let $f: V(G_1) \rightarrow V(G_2)$ be a function. Then a \emph{functigraph} $C(G, f)=(V, E)$ has the vertex set $V=V(G_1) \cup V(G_2)$ and the edge set $E=E(G_1) \cup E(G_2) \cup \{uv \mid v=f(u)\}$ . We study how metric dimension behaves in passing from $G$ to $C(G,f)$ by first showing that $2 \le \dim(C(G, f)) \le 2n-3$ , if $G$ is a connected graph of order $n \ge 3$ and $f$ is any function. We further investigate the metric dimension of functigraphs on complete graphs and on cycles.

preprint2012arXiv

On Zero Forcing Number of Functigraphs

\emph{Zero forcing number}, $Z(G)$ , of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G) \setminus S$ are colored white) such that $V(G)$ is turned black after finitely many applications of "the color-change rule": a white vertex is converted black if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank -- Special Graphs Work Group". Let $G_1$ and $G_2$ be disjoint copies of a graph $G$ and let $f: V(G_1) \rightarrow V(G_2)$ be a function. Then a \emph{functigraph} $C(G, f)=(V, E)$ has the vertex set $V=V(G_1) \cup V(G_2)$ and the edge set $E=E(G_1) \cup E(G_2) \cup \{uv \mid v=f(u)\}$ . For a connected graph $G$ of order $n \ge 3$ , it is readily seen that $1+δ(G) \le Z(C(G, σ)) \le n$ for any permutation $σ$ ; we show that $1+ δ(G) \le Z(C(G, f)) \le 2n-2$ for any function $f$ , where $δ(G)$ is the minimum degree of $G$ . We give examples showing that there does not exist a function $g$ such that, for every pair $(G,f)$ , $Z(G)<g(Z(C(G,f)))$ or $g(Z(G))>Z(C(G,f))$ . We further investigate the zero forcing number of functigraphs on complete graphs, on cycles, and on paths.

preprint2012arXiv

Probabilistic Zero Forcing in Graphs

The \emph{zero forcing number} $Z(G)$ of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G)\setminusS$ are colored white) such that $V(G)$ is turned black after finitely many applications of "the (classical) color change rule": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank - Special Graphs Work Group". We introduce here a probabilistic color change rule (pccr) which is a natural generalization of the classical color change rule. We introduce a theory of probabilistic zero forcing arising out of the pccr; the theory yields a quantity $P_A(G)$ , which can be viewed as the probability that a graph $G$ with an initial black set $A$ will be converted entirely to the color black. We also interpret the evolution of the sample spaces of this theory as a Markov process. We end with a few basic examples illustrating this theory.

preprint2011arXiv

Domination in Functigraphs

Let $G_1$ and $G_2$ be disjoint copies of a graph $G$ , and let $f: V(G_1) \rightarrow V(G_2)$ be a function. Then a \emph{functigraph} $C(G, f)=(V, E)$ has the vertex set $V=V(G_1) \cup V(G_2)$ and the edge set $E=E(G_1) \cup E(G_2) \cup \{uv \mid u \in V(G_1), v \in V(G_2), v=f(u)\}$ . A functigraph is a generalization of a \emph{permutation graph} (also known as a \emph{generalized prism}) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let $γ(G)$ denote the domination number of $G$ . It is readily seen that $γ(G) \le γ(C(G,f)) \le 2 γ(G)$ . We investigate for graphs generally, and for cycles in great detail, the functions which achieve the upper and lower bounds, as well as the realization of the intermediate values.

preprint2011arXiv

Iteration Index of a Zero Forcing Set in a Graph

Let each vertex of a graph G = (V(G), E(G)) be given one of two colors, say, "black" and "white". Let Z denote the (initial) set of black vertices of G. The color-change rule converts the color of a vertex from white to black if the white vertex is the only white neighbor of a black vertex. The set Z is said to be a zero forcing set of G if all vertices of G will be turned black after finitely many applications of the color-change rule. The zero forcing number of G is the minimum of |Z| over all zero forcing sets Z \subseteq V (G). Zero forcing parameters have been studied and applied to the minimum rank problem for graphs in numerous articles. We define the iteration index of a zero forcing set of a graph G to be the number of (global) applications of the color-change rule required to turn all vertices of G black; this leads to a new graph invariant, the iteration index of G - it is the minimum of iteration indices of all minimum zero forcing sets of G. We present some basic properties of the iteration index and discuss some preliminary results on certain graphs.

Cong X. Kang

Research overview

Is this your work?

16 publications

Distance- $k$ locating-dominating sets in graphs

Maker-Breaker Metric Resolving Games on Graphs

The Simultaneous Fractional Dimension of Graph Families

Maker-Breaker resolving game

On Laplacian Monopoles

The connected metric dimension at a vertex of a graph

The fractional $k$ -metric dimension of graphs

The fractional strong metric dimension in three graph products

A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs

On Domination Number and Distance in Graphs

Metric Dimension and Zero Forcing Number of Two Families of Line Graphs

On Metric Dimension of Functigraphs

On Zero Forcing Number of Functigraphs

Probabilistic Zero Forcing in Graphs

Domination in Functigraphs

Iteration Index of a Zero Forcing Set in a Graph

See the researcher in context

Building this map preview

Cong X. Kang

Research overview

Is this your work?

16 publications

Distance-kkk locating-dominating sets in graphs

Maker-Breaker Metric Resolving Games on Graphs

The Simultaneous Fractional Dimension of Graph Families

Maker-Breaker resolving game

On Laplacian Monopoles

The connected metric dimension at a vertex of a graph

The fractional kkk-metric dimension of graphs

The fractional strong metric dimension in three graph products

A Comparison between the Zero Forcing Number and the Strong Metric Dimension of Graphs

On Domination Number and Distance in Graphs

Metric Dimension and Zero Forcing Number of Two Families of Line Graphs

On Metric Dimension of Functigraphs

On Zero Forcing Number of Functigraphs

Probabilistic Zero Forcing in Graphs

Domination in Functigraphs

Iteration Index of a Zero Forcing Set in a Graph

See the researcher in context

Building this map preview

Distance- $k$ locating-dominating sets in graphs

The fractional $k$ -metric dimension of graphs