-4
$\begingroup$

If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.

Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq w \in V$ with $N(v) = N(w)$?

(Note that the definition of $N(\cdot)$ implies that $v,w$ cannot be adjacent.)

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ There are tons of obvious examples: every balanced complete multipartite graph, etc. Heck, even a $4$-cycle. Definitely not research level. $\endgroup$
    – verret
    Commented Jan 16, 2019 at 8:40
  • $\begingroup$ The $4$-cycle is nice because it is the only cycle that has a pair of vertices sharing the neighbourhood. The number of graphs without any pair of vertices sharing the neighbourhood (apparently called mating graphs) is oeis.org/A004110. Enumerative results using modern methods can be found in arxiv.org/abs/0705.0042, it may be interesting to refine this to regular graphs. $\endgroup$
    – Martin Rubey
    Commented Jan 17, 2019 at 19:56

1 Answer 1

Reset to default
0
$\begingroup$

An example with $k = 4$ is the octahedron.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This has the additional property that for every $v$ there is a $w$ such that $N(v) = N(w)$. If we just want one pair $(v, w)$ with the property we can easily just make countless such graphs by first drawing $v, w$, their neighbors and the edges from $v$ and $w$ to said neighbors and then keep adding vertices and edges until the result is regular again $\endgroup$
    – Vincent
    Commented Jan 16, 2019 at 8:22
  • $\begingroup$ Why the downvote? I thought everybody loves Platonic solids? $\endgroup$
    – Vincent
    Commented Dec 30, 2019 at 20:57

Not the answer you're looking for? Browse other questions tagged .