0
$\begingroup$

By constant link, I mean for any vertices $v,w$ of a graph $G$, the subgraph of $G$ induced by the neighborhood of $v$ is isomorphic to the subgraph induced by the neighborhood of $w$.

$C_n + C_m$ satisfies these conditions for $m \neq n$, which I was the first example that I was able to come up with, but I'm finding it difficult to conceive of a connected graph with constant link which is not vertex transitive.

Is anything known on the existence or lack thereof of such graphs?

$\endgroup$
1
$\begingroup$

Well, any triangle-free regular graph has constant link. Or take the line graph of such a graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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