Dankelmann–Oellermann–Swart conjecture on average Steiner distance

Let GG be a connected graph of order nkn\geq k, and let μ(G)\mu(G) denote its average distance and μk(G)\mu_k(G) its average Steiner kk-distance. Dankelmann–Oellermann–Swart conjecture. For 3kn3\leq k\leq n,

μk(G)3k1k+1μ(G).\mu_k(G)\geq 3\frac{k-1}{k+1}\mu(G).

Equivalently, the smallest ratio μk(G)/μ(G)\mu_k(G)/\mu(G) is conjectured to be attained by the path. The source describes the corresponding lower-bound problem as open.

Sources & referencesView supporting material

Primary source

Yaping Mao, “Steiner Distance in Graphs–A Survey”, arXiv:1708.05779 (2017).

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.