Adding or removing some nodes and links with out changing the maximum degree of G. Here the minimum function is linear with respect to its layer dimension.
I understand that you are looking for a general formula, but is there a reason to expect that all graphs of dimension d will have the same size subset that can be deleted to give a graph of (d-1)? For instance consider a simple case of d = 2 and a tree with 4 vertices. If you delete one leaf from the tree now you have a path with only 3 vertices with dimension now d=1. Other larger graphs with d = 2 will generally require more than just one vertex to be deleted to go to d = 1.
However it seems like the proper way to consider your question is by restricting attention to graphs of the same size. To be specific with my counter-question: Is there a reason to believe that all graphs of dimension d with N vertices will have the same minimum function M(N) that is the number of vertices to be deleted to create a graph of dim = (d -1)? Some graphs of size (d, N) may require a minimum of M(N) = (N/4) vertices deleted, while others might only require only M(N) = floor(N/5) while others graphs might be hard to bring down to (d-1) and require M(N) = (N/4) + 37. Are you looking for the special case graph of size (d, N) that has the smallest number required deletions to go to (d-1)? Or are you looking for a more general pattern or formula that fits some kind of other criteria that was not defined in your question?
Thanks for the interesting question.
thank you for taking interest . This problem is NP complete for general graph. The problem can be studied for a particular graph with N vertices , or we can study this problem for two graphs of same size for comparing their plus and minus.
1. If the cost of a sensor in ( robot navigation problem) is costly , we try to minimize the number of sensors with few loss of nodes permitted. 2: if we have two family of graphs , this problem gives some input to select the best one. It is possible to find good applications also.
example : 1. If G is a cycle of any finite length L then we have delete one vertex to have metric dimension d-1. If G is a complete graph on N vertices then we have delete one vertex to have metric dimension d-1.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs