6
$\begingroup$

Take the unit $d$-cube with vertices $\{0,1\}^d$, and restrict to the vertices that lie between (or within one of) a pair of parallel hyperplanes. These vertices form a graph whose edges are the edges of the cube, i.e. there is an edge joining two vertices if they differ in one coordinate.

For example, if $d=3$ and the bounding hyperplanes are $x+2y+2z=1$ and $x+2y+2z=3$, then the graph is $P_5$ embedded as $(0,1,0)–(1,1,0)–(1,0,0)–(1,0,1)–(0,0,1)$.

Is anything known about such graphs? In particular, is anything known about their diameter (or the diameter of their connected components, for the disconnected ones)? Is there such a graph that has a connected component whose diameter exceeds $2d$, say?

$\endgroup$
2
  • 1
    $\begingroup$ You want to only consider slices which form connected graphs, I presume? It's very easy to make a disconnected slice, whose diameter is infinity. $\endgroup$ – user856 Jul 11 '13 at 11:56
  • $\begingroup$ Good question. What I am actually interested in is the diameters of the connected components. I’ll edit to clarify. $\endgroup$ – Robin Houston Jul 11 '13 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.