Source author record

D. Kuziak

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

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Computing the metric dimension of a graph from primary subgraphs

Let $G$ be a connected graph. Given an ordered set $W = \{w_1, w_2,\dots w_k\}\subseteq V(G)$ and a vertex $u\in V(G)$ , the representation of $u$ with respect to $W$ is the ordered $k$ -tuple $(d(u,w_1), d(u,w_2),\dots,$ $d(u,w_k))$ , where $d(u,w_i)$ denotes the distance between $u$ and $w_i$ . The set $W$ is a metric generator for $G$ if every two different vertices of $G$ have distinct representations. A minimum cardinality metric generator is called a \emph{metric basis} of $G$ and its cardinality is called the \emph{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 for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.

preprint2012arXiv

Coloring, location and domination of corona graphs

A vertex coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that every two adjacent vertices of $G$ have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. 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 structures of a graph satisfying some domination property together with other conditions on the vertices of $G$ . In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance- $k$ colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, throughout some relationships between the distance- $k$ chromatic number of corona graphs and the distance- $k$ chromatic number of its factors. Moreover, we give the exact value of the distance- $k$ chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating-domination number of corona graphs. We give closed formulaes for the $k$ -domination number, the distance- $k$ domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.

preprint2010arXiv

Corrections to the article "The metric dimension of graph with pendant edges" [Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008) 139--145]

We show that the principal results of the article "The metric dimension of graph with pendant edges" [Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008) 139--145] do not hold. In this paper we correct the results and we solve two open problems described in the above mentioned paper.

preprint2010arXiv

On the metric dimension of corona product graphs

Given a set of vertices $S=\{v_1,v_2,...,v_k\}$ of a connected graph $G$ , the metric representation of a vertex $v$ of $G$ with respect to $S$ is the vector $r(v|S)=(d(v,v_1),d(v,v_2),...,d(v,v_k))$ , where $d(v,v_i)$ , $i\in \{1,...,k\}$ denotes the distance between $v$ and $v_i$ . $S$ is a resolving set for $G$ if for every pair of vertices $u,v$ of $G$ , $r(u|S)\ne r(v|S)$ . The metric dimension of $G$ , $dim(G)$ , is the minimum cardinality of any resolving set for $G$ . Let $G$ and $H$ be two graphs of order $n_1$ and $n_2$ , respectively. The corona product $G\odot H$ is defined as the graph obtained from $G$ and $H$ by taking one copy of $G$ and $n_1$ copies of $H$ and joining by an edge each vertex from the $i^{th}$ -copy of $H$ with the $i^{th}$ -vertex of $G$ . For any integer $k\ge 2$ , we define the graph $G\odot^k H$ recursively from $G\odot H$ as $G\odot^k H=(G\odot^{k-1} H)\odot H$ . We give several results on the metric dimension of $G\odot^k H$ . For instance, we show that given two connected graphs $G$ and $H$ of order $n_1\ge 2$ and $n_2\ge 2$ , respectively, if the diameter of $H$ is at most two, then $dim(G\odot^k H)=n_1(n_2+1)^{k-1}dim(H)$ . Moreover, if $n_2\ge 7$ and the diameter of $H$ is greater than five or $H$ is a cycle graph, then $dim(G\odot^k H)=n_1(n_2+1)^{k-1}dim(K_1\odot H).$

preprint2010arXiv

The partition dimension of corona product graphs

Given a set of vertices $S=\{v_1,v_2,...,v_k\}$ of a connected graph $G$ , the metric representation of a vertex $v$ of $G$ with respect to $S$ is the vector $r(v|S)=(d(v,v_1),d(v,v_2),...,d(v,v_k))$ , where $d(v,v_i)$ , $i\in \{1,...,k\}$ denotes the distance between $v$ and $v_i$ . $S$ is a resolving set of $G$ if for every pair of vertices $u,v$ of $G$ , $r(u|S)\ne r(v|S)$ . The metric dimension $dim(G)$ of $G$ is the minimum cardinality of any resolving set of $G$ . Given an ordered partition $Π=\{P_1,P_2, ...,P_t\}$ of vertices of a connected graph $G$ , the partition representation of a vertex $v$ of $G$ , 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)$ , $1\leq i\leq t$ , represents the distance between the vertex $v$ and the set $P_i$ , that is $d(v,P_i)=\min_{u\in P_i}\{d(v,u)\}$ . $Π$ is a resolving partition for $G$ if for every pair of vertices $u,v$ of $G$ , $r(u|Π)\ne r(v|Π)$ . The partition dimension $pd(G)$ of $G$ is the minimum number of sets in any resolving partition for $G$ . Let $G$ and $H$ be two graphs of order $n_1$ and $n_2$ respectively. The corona product $G\odot H$ is defined as the graph obtained from $G$ and $H$ by taking one copy of $G$ and $n_1$ copies of $H$ and then joining by an edge, all the vertices from the $i^{th}$ -copy of $H$ with the $i^{th}$ -vertex of $G$ . Here we study the relationship between $pd(G\odot H)$ and several parameters of the graphs $G\odot H$ , $G$ and $H$ , including $dim(G\odot H)$ , $pd(G)$ and $pd(H)$ .

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.

D. Kuziak

Research overview

Is this your work?

5 publications

Computing the metric dimension of a graph from primary subgraphs

Coloring, location and domination of corona graphs

Corrections to the article "The metric dimension of graph with pendant edges" [Journal of Combinatorial Mathematics and Combinatorial Computing, 65 (2008) 139--145]

On the metric dimension of corona product graphs

The partition dimension of corona product graphs

See the researcher in context

Building this map preview