What is the girth and circumference of Q4 (4-dimensional cube, a graph on 16 vertices),how can I prove it?

Girth means the length of a shortest cycle,and circumference means the length of a longest cycle.

  • $\begingroup$ Sorry if ths is a silly question but What is Q4? $\endgroup$ – Jasser Oct 3 '14 at 16:17
  • $\begingroup$ it means 4-dimensional cube,with 16 vertices and 32 edges,Regular-4 $\endgroup$ – user133140 Oct 3 '14 at 16:27
  • $\begingroup$ What is the circumference of a 4D cube? The sum of the 3D volumes of its faces? Could you tell what you mean by the girth and circumference and say what you know yourself? $\endgroup$ – Joonas Ilmavirta Oct 3 '14 at 16:40

The girth is the length of the shortest cycle. This is probably the easier part of the question. What possible lengths can cycles have? If you just work your way up from the smallest possible length, you should be able to see which actually occur.

I'm going to write $abcd$ for $(a,b,c,d)$, the coordinates of a vertex, where each letter can be either $0$ or $1$. Note that adjacent vertices differ in exactly one coordinate.

You can't have a cycle of length less than $3$. Since adjacent vertices differ in exactly one coordinate there can't be any cycles of odd length. But you can have a cycle of length $4$ (e.g. $0000,0001,0011,0010,0000$).

The circumference is the length of the longest cycle.

If I were working with a normal cube (it saves a lot of writing) I could visit every vertex to get a cycle of length 8:

$000$ $001$ $011$ $010$ $110$ $111$ $101$ $100$ $000$

I can't do any better than this because I can't repeat vertices, so the circumference would be $8$. You might want to try extending this approach to your cube.

  • $\begingroup$ Q4 should be labeled by 4 digits I think,but I guess,I got the idea,thanks $\endgroup$ – user133140 Oct 3 '14 at 17:06
  • $\begingroup$ It should, yes. The three digit section is an example of finding the circumference of Q3 (mainly because it takes a lot less time to type than it would for Q4). The spoilered section on girth is about Q4, so I used four digits there. $\endgroup$ – Raoul Oct 3 '14 at 17:27

For $n\ge 2$, the $n$-cube has a Hamiltonian cycle. See for instance http://en.wikipedia.org/wiki/Hypercube_graph

  • 1
    $\begingroup$ Not quite an answer but worth a comment: every Hamiltonian cycle in an $n$-cube corresponds to a (cyclic) Gray code and you can find more information, including some clear explicit constructions, by searching on that name. $\endgroup$ – Steven Stadnicki Oct 3 '14 at 19:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.