Paper Info
Title
Connected Resolving Sets In Graphs
Abstract
For an ordered set W = {omega(1), omega(2), ..., omega(k)} of vertices and a vertex v in a connected graph G, the representation of v, with respect to W is the k-vector r(nu\W)= d(nu, omega(1)), d(nu, omega(2)), ... , d(nu, omega(k))), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph <W> induced by W is a connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). The relationship between bases and minimum connected resolving sets in a graph is studied. A connected resolving set W of G is a minimal connected resolving set if no proper subset of W is a connected resolving set. The maximum cardinality of a minimal connected resolving set is the upper connected resolving number cr(+)(G). The upper connected resolving numbers of some well-known graphs are determined. We present a characterization of nontrivial connected graphs of order n with upper connected resolving number n - 1. It is shown that for a pair a, b of integers with 1 less than or equal to a less than or equal to b there exists a connected graph G with cr(G) = a and cr(+)(G) = b if and only if (a, b) not equal (1, i) for all i greater than or equal to 2.
Year
Venue
Keywords
2003
ARS COMBINATORIA
distance, connected resolving set, connected resolving number, upper connected resolving number
Field
DocType
Volume
Graph,Discrete mathematics,Combinatorics,Mathematics
Journal
68
ISSN
Citations 
PageRank 
0381-7032
2
0.55
References 
Authors
0
2
Name
Order
Citations
PageRank
Varaporn Saenpholphat1305.60
Ping Zhang229247.70