Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Discrete Mathematics and Combinatorics
Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel
Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel
Theory and Applications of Graphs
For a simple connected graph G=(V,E) and a subset X of its vertices, let
d*(X) = max {dist}G(x,y): x,y ∈ X}
and let h*(G) be the largest k such that there are disjoint vertex subsets A and B of G, each of size k such that d*(A) = d*(B). Let h*(n) = min {h*(G): |V(G)|=n}. We prove that h*(n) =⌊(n+1)/3 ⌋, for n ≥ 6. This solves the homometric set problem restricted to the largest distance exactly. In addition we compare h*(G) with a respective function hdiam(G), where …