MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let we have a regular graph. I want to know if we can partition the vertex set of this graph while in any part there exist a vertex with all its neighborhood?

share|cite|improve this question
I find this question too imprecise to be interesting. How many parts do you want? There is such a partition into two parts iff the diameter is greater then 2. – Brendan McKay May 10 '14 at 14:36
I want to partition whole of the graph in this way. I mean, make a partition, in every part put a vertex with all its neighborhood, so in each part there exist exactly r vertices, where my graph is r_regular. – user50655 May 10 '14 at 14:51
Oh, you want each part to consist of a vertex and its neighbours, not just that it contains a vertex and its neighbours. – Brendan McKay May 11 '14 at 0:46

You are asking for a perfect 1-code, there is a largish literature. There is no characterization of the regular graphs which contain a perfect 1-code, but a useful necessary condition is the that the graph has $-1$ as an eigenvalue. The binary Hamming codes provide examples in the $d$-cube when $d+1$ is a power of two.

share|cite|improve this answer
Dear Godsil, Would you please send me a paper about perfect 1-code? This is my email address: – user50655 May 10 '14 at 16:26

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]
share|cite|improve this answer

Is it the case that for each integer $r \geq 2$ the graph $K_{r, r}$ does not admit such a partition? Let $\{V_1, V_2\}$ be a bipartition of $K_{r, r}$. Without loss of generality let $v \in V_1$. Then $v$ and all vertices in $V_2$ must occur in one part of the partition, leaving us with an independent set $V_1 - \{v\}$.

On the other hand, every complete graph satisfies your property, the partition being the graph itself.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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