Skip to main content
3 of 3
added 2 characters in body; added 1 characters in body

"minimal" embedding of bipartite graphs on a sphere

Here is an easy to pose problem I've encountered (but haven't been able to solve or disprove):

Let (V,E) be a bipartite graph with the following property – the girth of the graph (i.e. the length of the shortest loop) is equal to the diameter of the graph times 2. i.e. if we denote the girth $2n$ then the diameter is $n$.

For such a graph and call an embedding of the graph into a sphere $S^m$ a function $f:V\rightarrow S^m$ Such that there is a constant $k$ such that if $v_1$ and $v_2$ are connected by an edge then $d(f(v_1),f(v_2))=k$ when $d$ is the spherical distance (i.e. the length of the shortest geodetic segment on the sphere which connects $f(v_1)$ and $f(v_2)$).

Is the following claim true: does $k< \frac{ \pi}{n}$ implies that $f(V)$ is contained in a hemisphere?

Note that the settings are important - for any graph the answer is clearly no: take a triangle and embed it in the obvious way in a circle - so the diameter of the graph is 1 but the length of the arc between two vertices is $\frac{2 \pi}{3} < \frac{ \pi}{1}$ and the vertices are not contained in any half circle.

(One can say that I'm looking for a spherical Jung type theorem for bipartite graphs).