Skip to main content
bijective graph homomorphism -> graph isomorphism (subtle difference)
Source Link

Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of bijective graph homomorphismsgraph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\varphi, \psi \in \Aut(G)\text{ and } \{\varphi(v),\psi(v)\}\in E\text{ for all }v\in V\big\}.$$ So $\big(\Aut(G), E(\Aut(G)\big)$ is a simple, undirected graph.

Question. If $\kappa$ is a cardinal, is there a connected graph $G=(V,E)$ with $|V|\geq \kappa$ and $G \cong \Aut(G)$?

Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of bijective graph homomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\varphi, \psi \in \Aut(G)\text{ and } \{\varphi(v),\psi(v)\}\in E\text{ for all }v\in V\big\}.$$ So $\big(\Aut(G), E(\Aut(G)\big)$ is a simple, undirected graph.

Question. If $\kappa$ is a cardinal, is there a connected graph $G=(V,E)$ with $|V|\geq \kappa$ and $G \cong \Aut(G)$?

Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of graph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\varphi, \psi \in \Aut(G)\text{ and } \{\varphi(v),\psi(v)\}\in E\text{ for all }v\in V\big\}.$$ So $\big(\Aut(G), E(\Aut(G)\big)$ is a simple, undirected graph.

Question. If $\kappa$ is a cardinal, is there a connected graph $G=(V,E)$ with $|V|\geq \kappa$ and $G \cong \Aut(G)$?

edited tags
Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Source Link

Graphs $G$ with $G \cong \text{Aut}(G)$

Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of bijective graph homomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\varphi, \psi \in \Aut(G)\text{ and } \{\varphi(v),\psi(v)\}\in E\text{ for all }v\in V\big\}.$$ So $\big(\Aut(G), E(\Aut(G)\big)$ is a simple, undirected graph.

Question. If $\kappa$ is a cardinal, is there a connected graph $G=(V,E)$ with $|V|\geq \kappa$ and $G \cong \Aut(G)$?