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?
3
-
1$\begingroup$ 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. $\endgroup$– Brendan McKayCommented May 10, 2014 at 14:36
-
$\begingroup$ 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. $\endgroup$– user50655Commented May 10, 2014 at 14:51
-
$\begingroup$ Oh, you want each part to consist of a vertex and its neighbours, not just that it contains a vertex and its neighbours. $\endgroup$– Brendan McKayCommented May 11, 2014 at 0:46
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered May 10, 2014 at 15:25
-
$\begingroup$ Dear Godsil, Would you please send me a paper about perfect 1-code? This is my email address: [email protected] $\endgroup$ Commented May 10, 2014 at 16:26
$\begingroup$
$\endgroup$
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)]
$\begingroup$
$\endgroup$
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.
