Does there exist a connected graph $G$ and a bijection $\varphi: V(G) \to V(G)$ with the property that $d(u, v) = 2 \Leftrightarrow d(\varphi(u), \varphi(v)) = 2$, but $\varphi$ is not an automorphism? I haven't been able to come up with a counterexample, but I haven't been able to get a hold of a proof either.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Let $G$ be a line with three segments, i.e., $V=\{a,b,c,d\}$ and $E=\{\{a,b\},\{b,c\},\{c,d\}\}.$ Let $\varphi=\{(a,a),(b,d),(c,c),(d,b)\}.$ This is not an automorphism because it maps a vertex of degree $2$ to a vertex of degree $1,$ but it preserves the relationship "has distance $2$ to" between vertices.
-
1
-
1$\begingroup$ I was going to say "hexagon", but this is an even simpler bipartite example (+1). $\endgroup$– tkfCommented yesterday
-
1$\begingroup$ You mean a hexagon where the bijection rotates three of the six vertices, right? This example, as well as mine, both of them bipartite, would generalize to the following description: a graph with a proper colouring where at least one of the colours has the following two properties: (1) all vertices of that colour are at distance exactly 2 from one another; and (2) at least two vertices admit a non-automorphic bijection that fixes all vertices of other colours. A particular case of condition (2) is when two of those vertices have different degrees, because then a simple swap will do the trick. $\endgroup$– LievenCommented yesterday
-
1$\begingroup$ @Lieven I was actually thinking of just swapping two vertices that are distance 2 apart, rather than rotating three - but both fall under your paradigm. I think you need to extend condition 1 to "all vertices of that colour are at distance exactly 2 from one another AND not distance 2 to vertices of any other colour". e.g. consider the graph $1-2-3-4-5$. Then swapping $3$ and $5$ is not a valid example, because of the distances to $1$. $\endgroup$– tkfCommented yesterday