-1
$\begingroup$

Composition of two functions, ${f_1}$ and ${f_2}$, is commutative if ${f_1} \circ {f_2} = {f_2} \circ {f_1}$. Even when the functions are bijective, it is not necessary that their composition is commutative. My question is, given two specific bijective functions, isomorphism and complementation on a graph $G$, is their composition commutative?

I realized that if two graphs $G$ and $H$ are isomorphic, then their complements are also isomorphic. This led me to see (ref below proof by contradiction) that the above composition is commutative. Can anyone pls tell me if this is correct! It would be great if you could point out any other theory that has led to similar conclusion.

My reasoning: By contradiction, ${f_1} \circ {f_2} (G) \not= {f_2} \circ {f_1} (G)$.

$=> {f_1} ({f_2}(G))={f_1} (G^{c}) \not= {f_2} ({f_1} (G))= {f_2} (H) = H^{c}$
However, $H^{c}$ and $G^{c}$ are isomorphic.

$\endgroup$
10
  • $\begingroup$ I think not, take for example a graph G and a graph H, which is equal to G with one more distinct vertex w (no edges between w to the other vertices). $\endgroup$
    – friedvir
    Commented Oct 3, 2019 at 9:09
  • $\begingroup$ @friedvir - In that case, are G and H isomorphic! $\endgroup$
    – KGhatak
    Commented Oct 3, 2019 at 9:33
  • $\begingroup$ Sorry didn't notice, then i guess you are right, just need the explanation for why the complement graphs are isomorphic, won't be hard to prove $\endgroup$
    – friedvir
    Commented Oct 3, 2019 at 9:44
  • 1
    $\begingroup$ I don't understand what is meant by "the function represents complementation". What are the domain and range of the function $f_2$ (vertex sets? edge sets?) and how does it act? $\endgroup$
    – bof
    Commented Oct 7, 2019 at 5:59
  • 1
    $\begingroup$ I understand perfectly well what the complement of a graph is, but I don't know what function you are talking about. For instance, if $G$ has vertex set $V=\{w,x,y,z\}$ and edge set $E=\{wx,xy,yz,wz\}$, then $G^c$ has vertex set $\{w,x,y,z\}$ and edge set $\{wy,xz\}$. But what is the function $f_2:G\to G^c$ that you are talking about? What is $f_2(w)$? Is $f_2$ just the identity map on $V$? $\endgroup$
    – bof
    Commented Oct 7, 2019 at 6:31

1 Answer 1

1
+50
$\begingroup$

If you try to think of the operation of complementation as a function you are making things harder to understand than they need to be. You would have to carefully define a class of 'all' graphs. Whether it is an isomorphism on such a class is not relevant to your actual question as I understand it.

If $G$ and $H$ are finite simple graphs and $\varphi: G \rightarrow H$ is a graph isomorphism then $\varphi(G)^C = \varphi(G^C)$ because these two graphs have the vertices and the same edges. So you could say that complementation and applying the isomorphism commute.

$\endgroup$

You must log in to answer this question.

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