The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2020: Metric Dimension

G
Topic
First Poster
Last Poster
Fan graph (3,2)
Aser   4
N Oct 25, 2020 by JGeneson
In this research paper, https://mp.feri.um.si/osebne/peterin/clanki/edimproduct5.pdf
Theorem 1: For any non trivial graphs G and H,
edim(G ∨ H) = { |V (G)| + |V (H)| − 1, if G ∈ G or H ∈ G,
|V (G)| + |V (H)| − 2, if G, H /∈ G.
As a corollary based on this theorem, a complete bipartite graph G2,2 has edim (G) = 2, and any multipartite graph G(,ri,r2,...rn) with k larger than 2 will have edim(G) = ∑(ri-1) with i = [1,n]. This implies that the tripartite G(1,1,3) will have edim(G)=2, and this tripartite graph is also a fan graph (3,2). The rules for fan graphs in resource 3 are only for fan graphs (1,n), so I am not sure of my undertaking.

P.S. Because I can't write mathematical notations here, I would prefer you read it from the original research paper. The theorem is in page 3 and the corollary is in page 4
4 replies
Aser
Oct 10, 2020
JGeneson
Oct 25, 2020
No edges?
MathPotato222   1
N Oct 3, 2020 by JGeneson
Hi, I'm new to CrowdMath but find this really cool!
Is this problem the graphs with no edges?
No edges means if there are 2 vertices with no landmarks, they both have distance infinity to all others, so there can only be one vertex with no landmark.
This can be constructed with n vertices, n-1 of them have a landmark.
Case 1:
The robot's distance to some landmark is 0, so it knows where it is.
Case 2:
The robot's distance to every landmark is infinity, so it must be on the one node without a landmark.

Is this correct? I know this must be one of the simpler problems but during this pandemic I've really been missing my college problem solving group and I'd love to join this! : )
1 reply
MathPotato222
Sep 30, 2020
JGeneson
Oct 3, 2020
No more topics!
a