# Is there any partition of a regular graph which in any part there exists a vertex with all its neighborhood?

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?

-
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.

-
Dear Godsil, Would you please send me a paper about perfect 1-code? This is my email address: mina_hmfzmaf@yahoo.com – 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)]

-

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.

-