Bijective operations on finite simple graphs

Question

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.

I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An example for what I have in mind would be the graph complement. Another example is to decompose the graph into connected components, and complement those components whose complement is connected.

Note that an easier variant of the same question is obtained by dropping the requirement that the map be bijective. Various graph powers then serve as examples.

This is a follow-up question on equidistributed parameters on graphs: for any map (bijective or not), we can check whether it affects various graph parameters in interesting ways.

Answer 1

A 3-connected planar graph has a unique embedding in the plane (see https://en.wikipedia.org/wiki/Dual_graph#Uniqueness). And the planar dual of a 3-connected planar graph is again 3-connected. So you define an involution on the set of graphs which acts trivially if the graph is not 3-connected and planar, and replaces 3-connected planar graphs by their duals.

Answer 2

One can also cook up an involution based on unique factorization of connected graphs under various products. A connected graph has a unique representation as a cartesian product of irreductible graphs (connected graphs that cannot be further factored). This was proven by Sabidussi and independently by Vizing. Starting with an arbitrary graph $G$ you can look at the connected components, factor them into irreducibles and then complement each irreducible factor if it has a connected complement, otherwise leave it alone. You can do the same with the strong graph product, for which unique factorization of connected graphs was proven by Dorfler and Imrich and independently by McKenzie.

I wanted to comment a little on your suspicion that there are not many natural maps $f_n:\mathcal G_n\to\mathcal G_n$. One (very restrictive) way to formalize this would be to add the requirement that $f_n$ be "continuous" in the sense that if $H_1$ and $H_2$ differ only by an edge, then $f_n(H_1)$ and $f_n(H_2)$ also differ only by one edge. This can be formalized by defining a graph structure on $\mathcal G_n$ itself, with an edge $H_1\leftrightarrow H_2$ if $H_1=H_2+e$. Then a continuous bijection as mentioned above is simply a graph automorphism of this graph.

The yoga around graph reconstruction is all about expecting such objects to have very few automorphisms. For example if we enrich the graph on $\mathcal G_n$ above with an orientation (say edges are oriented in the direction where the number of edges increases) then the set edge reconstruction conjecture implies that this directed graph has no nontrivial automorphisms (a topic of this older question). Without the orientation we pick up one automorphism which is taking complements but it's natural to expect that these two are the only automorphisms! In other words if you believe the various reconstruction conjectures you should probably believe that the identity and taking complements are the only two "continuous" bijections on $\mathcal G_n$.

One can go one step further and make the conjecture that the identity and taking complements are the only "local" bijections $\mathcal G_n \to \mathcal G_n$, in the sense that you can decide how you transform the graph locally without having to look further than a fixed distance from your current location.

Answer 3

Well, this is not quite an answer but it may still be helpful and is too long for the comments

The mapping $f: \mathcal{G}_n \mapsto \mathcal{G}_n$ where $f(G)$ is the complement of $G$ on each connected component of $G$, is not a bijection though.

Indeed, let $H_1$ be the graph on $[n]$ and assume $n$ is a multuple of 5, where the connected components of $H_1$ are $\{5k+1,\ldots, 5k+5\}$; $k=0,\ldots, \frac{n}{5}-1$ (so $H_1$ has $\frac{n}{5}$ connected components of size 5 each). Let $H_1$ on each of those connected components $\{5k+1,\ldots, 5k+5\}$ be a 5-cycle $C_k$ for each $k=0,1,\ldots, \frac{n}{5}-1$ [and $H_1$ has no other edges).

Now let $H_2$ be the complete graph on $[n]$ minus for each $k=0,\ldots, \frac{n}{5}-1$ the complete graph on $\{5k+1,\ldots, 5k+5\}$ but then added back the edges in the $C_k$s where the $C_k$s are as above in $H_1$. So $H_2$ is still connected.

Note that $f(H_1)=f(H_2)$; indeed $f(H_1) \doteq G$ is the graph where for each $k$, the graph $G$ on $\{5k+1,\ldots, 5k+5\}$ is the complete graph on these 5 vertices minus $C_k$ as defined above, and $f(H_2)$ is $G$ as well.

---

An even simpler example is to let $H_1$ be the graph on $[n]$ with no edges (each vertex is its own connected component), and let $H_2$ be the complete graph.

Answer 4

Inspired by the question Regular graph such that $2$ distinct vertices have same neighborhood set, and via https://oeis.org/A004110, I discovered the following article presenting an apparently very non-trivial bijection on graphs:

Kilibarda, Goran, Enumeration of unlabelled mating graphs, Graphs Comb. 23, No. 2, 183-199 (2007). ZBL1116.05038.