• English
    • français
  • English 
    • English
    • français
View Item 
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • James D. Currie
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The metric dimension and metric independence of a graph

Thumbnail

View Open

Article (pdf) (181.5Kb)

Metadata

Show full item record

Author

Currie, James
Oellerman, Ortrud R.

Uri

http://hdl.handle.net/10680/1746

Date

2001

Citation

Currie, James, and Ortrud R. Oellerman, "The metric dimension and metric independence of a graph," Journal of Combinatorial Mathematics and Combinatorial Computing 39 (2001): 157–167.

Abstract

A vertex x of a graph G resolves two vertices u and v of G if the distance from x to u does not equal the distance from x to v. A set S of vertices of G is a resolving set for G if every two distinct vertices of G are resolved by some vertex of S. The minimum cardinality of a resolving set for G is called the metric dimension of G. The problem of nding the metric dimension of a graph is formulated as an integer pro- gramming problem. It is shown how a relaxation of this problem leads to a linear programming problem and hence to a fractional version of the metric dimension of a graph. The linear programming dual of this problem is considered and the solution to the corresponding integer programming problem is called the metric independence of the graph. It is shown that the problem of deciding whether, for a given graph G, the metric dimension of G equals its metric independence is NP- complete. Trees with equal metric dimension and metric independence are characterized. The metric independence number is established for various classes of graphs.

Collections

  • James D. Currie
  • Ortrud Oellerman

Description

Preprint

Report a copyright concern

Contact Us | Send Feedback
 

 

Browse

All of WinnSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Report a copyright concern

Contact Us | Send Feedback