Conjecture on starting-vertex variability of the nearest unvisited vertex walk
Statement
Let be a finite graph, let be a uniformly random initial vertex, and let denote the length of the nearest unvisited vertex walk started at . Write for its standard deviation and for its expectation. Starting-vertex variability conjecture. The ratio
is bounded over all finite graphs. This asks whether the variability caused by choosing the initial vertex uniformly is uniformly controlled, modifying the preceding question about the ratio of the maximum and minimum walk lengths; no resolution is given.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.