Y by Adventure10
Here is a construction for a graph with metric dimension which contains a .
Start with a , and label each vertex with a binary coordinate of length . Then for each pair , we construct new vertices as follows.
Given some :
- is an edge if and
- is an edge if and
- is an edge if and
- is an edge if and
Then we claim that the set of all 's is an edge metric basis for .
Let be the set of new vertices and supposed that for edges . If is adjacent to some new vertex, then must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of be , and the other endpoint of be . For each pair , and are distance 1 from exactly one of the 's, meaning and for all pairs . Thus, .
If are not adjacent to some new vertex, then write
.
Lemma: For each pair , if the pairs and are not identical, then must be adjacent to two of the 's. Then must also be adjacent to the same ones, so we have either and , or the other way around: and
For to be an edge, there must be some coordinate where . By applying the lemma on and , either or . WLOG let and . Then, for each , we can apply the lemma on and . Since , we must have , and in particular, . Similarly, , so .
Thus, and , meaning .
This construction means that a graph with edim can at a minimum contain a with on the order of .
Note: I think the vertices might not be necessary?
Start with a , and label each vertex with a binary coordinate of length . Then for each pair , we construct new vertices as follows.
Given some :
- is an edge if and
- is an edge if and
- is an edge if and
- is an edge if and
Then we claim that the set of all 's is an edge metric basis for .
Let be the set of new vertices and supposed that for edges . If is adjacent to some new vertex, then must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of be , and the other endpoint of be . For each pair , and are distance 1 from exactly one of the 's, meaning and for all pairs . Thus, .
If are not adjacent to some new vertex, then write
.
Lemma: For each pair , if the pairs and are not identical, then must be adjacent to two of the 's. Then must also be adjacent to the same ones, so we have either and , or the other way around: and
For to be an edge, there must be some coordinate where . By applying the lemma on and , either or . WLOG let and . Then, for each , we can apply the lemma on and . Since , we must have , and in particular, . Similarly, , so .
Thus, and , meaning .
This construction means that a graph with edim can at a minimum contain a with on the order of .
Note: I think the vertices might not be necessary?
This post has been edited 1 time. Last edited by ChocolateMangoes, Feb 6, 2020, 5:51 AM