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.

  • $\begingroup$ What exactly are you looking for? "Natural" _involutions_on $\mathcal G_n$? Or some involutions/bijections bearing some other interesting properties (which?)? $\endgroup$ – Ilya Bogdanov Oct 23 '18 at 20:16
  • $\begingroup$ @IlyaBogdanov: the main reason for my curiosity comes from mathoverflow.net/q/312823/3032, and the suspicion that the reason for not having any equidistribution results on $\mathcal G_n$ is that there are hardly any natural maps. I must admit that it took me a while to come up with the second example (complement if connected), apart from the graph complement. In fact, I'd be more interested in maps which are not involutions. They should be somewhat natural, though. $\endgroup$ – Martin Rubey Oct 23 '18 at 20:25

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.

  • $\begingroup$ That's a nice contribution! Possibly one can even define something like a $3$-connected decomposition. $\endgroup$ – Martin Rubey Jan 18 at 19:08
  • $\begingroup$ (can you come up with something that isn't an involution, too? :-) $\endgroup$ – Martin Rubey Jan 18 at 19:25
  • 1
    $\begingroup$ @MartinRubey: It might be possible to similarly define an order 3 map from "Tutte's Trinity Theorem" $\endgroup$ – Sam Hopkins Jan 18 at 19:33

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.

  • $\begingroup$ I think in the first paragraph it should say "complement each irreducible factor if it has an irreducible complement". $\endgroup$ – Martin Rubey Jan 19 at 7:34
  • $\begingroup$ Your first idea gives rise to many bijections: instead of complementing irreducible factors, we can of course also fix an arbitrary bijection on them, and also control some properties. For example, exchange all paths with stars, etc. $\endgroup$ – Martin Rubey Jan 19 at 8:18

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.

  • $\begingroup$ I am sorry, but I do not understand. Yes, the map taking the complement of each component is not a bijection, but I didn't claim that. Please clarify! $\endgroup$ – Martin Rubey Jan 18 at 18:59
  • $\begingroup$ Well, but I am only going by the 2nd paragraph in your original question: "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." $\endgroup$ – Mike Jan 18 at 19:02
  • $\begingroup$ Yes. So the image of the complete graph would be the complete graph (because it's complement is not connected). Am I missing something? $\endgroup$ – Martin Rubey Jan 18 at 19:10
  • $\begingroup$ I'm not seeing that. The phrase "complement those components whose complement is connected" did seem to be a mouthful and wasn't clear, to me at least. Going back to the complete graph, the complement is the graph w no edges, so each vertex is its own component. So what do you do next? $\endgroup$ – Mike Jan 18 at 19:15
  • $\begingroup$ The first occurrence of 'complement' in the phrase was intended as a verb, sorry for not being clearer. Thus: 1. decompose into connected components 2. for each connected component check whether it's complement is connected 2.a if it is, take the complement of this component 2.b if it isn't, leave it as is. $\endgroup$ – Martin Rubey Jan 18 at 19:21

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.

  • $\begingroup$ Why the downvote? $\endgroup$ – Martin Rubey Feb 8 at 19:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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