Relations between Metric Dimension and Domination Number of Graphs

Details Relations between Metric Dimension and Domination Number of Graphs Relations between Metric Dimension and Domination Number of Graphs

2011-12-11

arxiv.org/abs/1112.2326v1

Mathematics

Combinatorics

6 pages

Scientific paper

A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\neq d(v,w)$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$, and denoted by $\beta(G)$. In this paper, we prove that in a connected graph $G$ of order $n$, $\beta(G)\leq n-\gamma(G)$, where $\gamma(G)$ is the domination number of $G$, and the equality holds if and only if $G$ is a complete graph or a complete bipartite graph $K_{s,t}$, $ s,t\geq 2$. Then, we obtain new bounds for $\beta(G)$ in terms of minimum and maximum degree of $G$.

Affiliated with

Also associated with

No associations

Rating

Relations between Metric Dimension and Domination Number of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relations between Metric Dimension and Domination Number of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relations between Metric Dimension and Domination Number of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306823