A resolving set of a graph G is a subset of nodes of V(G) through which , we can distinguish between any two nodes in G. Resolving set of minimum cardinality is called metric basis and cardinality of a metric basis is called metric dimension of G. Graph with multiple metric bases has more advantages than a graph with unique metric basis. Assume the situation where many sensor nodes are connected in the surface of a big planet like Jupiter through a suitable discrete space. A robot that moving in this discrete space can able find its closest land marks(Elements in a metric bases) to know its locations uniquely, This is possible, when the discrete space has multiple metric bases. This robot need not depend on landmarks that are very for away from it. For further research in this NP hard problem we look for a graph G with n- nodes having metric dimension n/2.
C_4 and K_4^- :) but that isn't very interesting, I'll try to think of better examples
Thank You Dr. James. Looking for non-trivial graph Family from one of the Good researchers like you.
Thak you Dr.James. Though this new family satisfy our conditions but it fails to satisfy the expected second condition that every subset of cardinality dim(G) is a metric basis.
Ah, but that was a different question ;) That question is actually open - will post an answer on the other page
Is it possible to get a non-symmetrical graph that has dim(G)=n/2 and non-isomorphic metric bases count equal to upper bound B(G), with a condition that B(G) is maximum with respect to given n ?
If you also want them to be non-isomorphic, then it is unknown if you can hit the upper bound B(G) at all. I would guess that it is not possible in the case that you describe.
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publications