On the graphical containment of discrete metric spaces (Q1332434)

An undirected graph \(G= (V, E)\) (without loops) contains a discrete metric space \(M= (U, d)\) if \(U\subseteq V\) and for all \(u\), \(v\in U\), \(d(u, v)= d_ G(u, v)\), where \(d_ G(u, v)\) is the length of a shortest path in \(G\) from \(u\) to \(v\). For a discrete metric space \(M= (U, d)\) put \[ g(M)= \min\{| V|- | U|: G= (V, E) \text{contains} M\}. \] It is proved that for \(M_{q,k}\) being a metric space on \(k\) elements every two of them of distance \(q\) apart, it holds \(g(M_{q, k})= [(q- 1)/2] k+ (q- 1) \text{ mod }2.\) (\([x]\) denotes the greatest integer \(\leq x\).) A graph \(G= (V, E)\) is a minimum container of \(M= (U, d)\), denoted by \(G^*(U, d)\), provided \(| V|= | U|+ g(M)\); \(m(G)= \min\{| U|: G^*(U, d)\}\). It is proved that (1) \(m(G)= 2\) iff \(G\) is a path; (2) if \(C_ n\) is a circuit on \(n\geq 4\) elements, then \(m(C_ n)= 4\); (3) for a tree \(T\) with \(e\) leaves, \(m(T)= e\).