The metric dimension of the supertoken graph of the complete graph

About 2 years old · traced to

Let Fk(Kn){\cal F}_k(K_n) be the supertoken graph whose vertices represent configurations of kk indistinguishable tokens on the complete graph KnK_n, with adjacency given by moving one token along an edge of KnK_n. The metric dimension of a graph is the minimum cardinality of a resolving set, namely a set of vertices whose distance vectors distinguish all vertices.

Metric-dimension conjecture. The metric dimension of the supertoken graph Fk(Kn){\cal F}_k(K_n) is

dim⁡(Fk(Kn))=n−1.\operatorname{dim}({\cal F}_k(K_n))=n-1.

The preceding proposition establishes the upper bound dim⁡(Fk(Kn))≤n−1\operatorname{dim}({\cal F}_k(K_n))\leq n-1; the conjecture asserts that this bound is sharp. The supplied text does not provide a lower-bound proof or evidence of resolution.

References

Primary source

E. T. Baskoro, C. Dalfó, M. A. Fiol and R. Simanjuntak, “On some metric properties of supertoken graphs”, arXiv:2412.20558 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.