Extremal Graph Theory for Metric Dimension and Girth

Details Extremal Graph Theory for Metric Dimension and Girth Extremal Graph Theory for Metric Dimension and Girth

2012-03-07

arxiv.org/abs/1203.1584v2

Mathematics

Combinatorics

6 pages

Scientific paper

A set $W\subseteq V(G)$ is called a resolving set for $G$, 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, it is proved that in a connected graph $G$ of order $n$ which has a cycle, $\beta(G)\leq n-g(G)+2$, where $g(G)$ is the length of a shortest cycle in $G$, and the equality holds if and only if $G$ is a cycle, a complete graph or a complete bipartite graph $K_{s,t}$, $ s,t\geq 2$.

Affiliated with

Also associated with

No associations

Rating

Extremal Graph Theory for Metric Dimension and Girth 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 Extremal Graph Theory for Metric Dimension and Girth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Graph Theory for Metric Dimension and Girth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-395578