Demo*graph*ics

A \(k\)-regular graph satisfies the neighborhood diversity condition if it is possible to label each vertex with one of \(1, 2, 3, \ldots, k\) such that for each vertex, all its neighbors have different labels.

Determine the sum of all \(n\) satisfying \(1 \le n \le 1000\) such that the \(n\)-hypercube graph satisfies the neighborhood diversity condition.

\(\)
Clarification:

  • In a \(k\)-regular graph, each vertex has \(k\) neighbors.
  • An \(n\)-hypercube graph is the graph of an \(n\)-dimensional hypercube. In other words, its vertices are elements of \(\{0,1\}^n\) (that is, \(n\)-tuples with each component 0 or 1), and two vertices are adjacent if and only if they differ in exactly one component.
  • The labeling is not necessarily a proper vertex coloring: two adjacent vertices may have the same label.
×

Problem Loading...

Note Loading...

Set Loading...