A resolving set of a graph G is a subset of nodes of Vertex set V(G) through which , we can distinguish any two nodes in G. Resolving set of minimum cardinality is called metric basis of G and cardinality of a metric basis is called metric dimension of G. Here Kn is a complete graph on n vertices.
This is raised as an open question in the new paper 'on the metric bases of graphs' by Korivand, Baskoro & Erskine. They show that any such graph must be asymmetric, and there are no graphs with this property up to order 10 (the best has order 8, with 76.8% of the sets in question being metric bases). I would guess that there are no such graphs, but would be delighted to be proved wrong.
Korivand Research Team focus only non-isomorphic metric bases count. We focus on all possible metric bases count (BIGS index). Any complete graph will have only one non-isomorphic metric basis and they reported B(G)=1. But in our case considering all possible metric bases(Isomorphic and non-isomorphic metric bases ) , then BIGS(G) =upper bound = n c(dim(G)) =n. And we look for another family of graphs having maximum Metric Bases count =nc(dim(G)). And more over we can extract all metric bases almost all graphs expect few like HDN3 and PHDN3 as the number of combinations are very big number.
We appreciate your valuable time and the effort you are dedicating to us
One observation: any such graph must be twin free. By the way, it seems to me that stars do not have this property - consider a set that is missing just two of the leaves?
There are many Odd cycles (Example: C5) have isomorphic and non-isomorphic metric bases count equal to n c dim(G) ( which is eqaul to upper bound of BIGS(G)). but clearly we can see C5 has only B(G)=2(non-isomorphic Metric bases count) , but this is not equal to ( n c dim(G)) where as the total matric bases count =( n c dim(G))=10 for C5.
Yes, and more generally for C_{2d+1} there will be d different such metric bases up to automorphism equivalence. But I thought in this case you were interested in the total number, not up to automorphism?
If nc(dim(G) is never equal to B(G) ( Non-isomorphic metric bases count) then nc(dim(G) is not a better upper bound for B(G). A new formula is yet to be found.
- Badges
- Science topic