-3
$\begingroup$

Let's call a simple, undirected graph $G=(V,E)$ homogeneous if for every $v,w\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(v)=w$.

It is clear that every finite homogeneous graph is $k$-regular for some $k\in\mathbb{N}$.

Is there $k\in\mathbb{N}$ and a connected $k$-regular graph that is not homogeneous?

(The smallest example of a $2$-regular graph that is not homogenous is the disjoint union of $K_3$ and $C_5$, but in this question I'm focusing on connected graphs.)

$\endgroup$
1
  • $\begingroup$ Ask Google about "vertex-transitive graphs". $\endgroup$
    – Wolfgang
    Commented May 9, 2016 at 13:47

1 Answer 1

2
$\begingroup$

Homogeneous is usually called vertex transitive. Not all connected regular graphs are vertex transitive. For example, the Frucht graph is a 3-regular connected graph that is not vertex transitive (its automorphism group is the identity).

$\endgroup$

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