Let $G$ be a simple graph and $S$ be the set of all sub graphs of $G$. Define two operations on $S$ as: $union$ of two graphs $ G_1$ and $G_2$ is, $G_1\cup G_2$

$=\langle V(G_1)\cup V(G_2), (E(G_1)\cup E(G_2)\rangle$

and the graphs $intersection$ is, $G_1\cap G_2$

$=\langle V(G_1)\cap V(G_2), (E(G_1)\cap E(G_2)\rangle$.

Let $P(S)$ be the power set of $ S$ and for any two subsets of $S$ namely, $ A, B\in P(S)$, define:

$A\sqcup B=\lbrace G_i\cup G_j:~G_i\in A, G_j\in B\rbrace$ and

$A\sqcap B=\lbrace G_i\cap G_j:~G_i\in A, G_j\in B\rbrace$. Also, consider a mapping

$ f: S\rightarrow P(S)$ such that $f(empty~ graph)= emptyset $ and $f( G)=S$.

So, how should $f$ be defined so that it is a homomorphism keeping in mind that every element of $ S$ is a graph while every element of $P(S)$ is a subset containing graphs?

  • $\begingroup$ I hope it is not a stupid question. What do you consider a homomorphism in this case? $\endgroup$ Sep 19 '19 at 21:44
  • $\begingroup$ @user2679290 Even breakthrough results were borned out of stupid questions only. So, please bear. $\endgroup$
    – gete
    Sep 20 '19 at 1:27

A possible answer is the following, if you are willing to relax the definitions (in a very minor way) of union and intersection of two graphs.

For clarity, let me introduce an additional notation. For any subgraph $H$ of $G$, considered as a graph with vertex set $V(G)$ (this is trivially possible by adding those vertices of $G$ into $H$, which do not participate in the edge set of $H$), let $Q_G(H)$ be the set of all subgraphs of $H$, where again the vertex set of each graph in $Q_G(H)$ is $V(G)$ (hence the subscript $G$ in $Q_G$).

Define the union and intersection of two graphs in $Q_G(G)$ as you have defined for the edge set, but now over vertex set $V(G)$. Now the map $f:Q_G(G)\to P(Q_G(G))$ defined by $f(H)=Q_G(H)$ should give you the desired homomorphism.

  • $\begingroup$ In that case $Q_G(G)\subseteq S$. Right? $\endgroup$
    – gete
    Sep 20 '19 at 13:29
  • $\begingroup$ They'll be essentially equal. Every graph H in S will be in Q_G(G), however,the vertex set of H will not be V(H) but instead V(G). $\endgroup$
    Sep 20 '19 at 13:54
  • $\begingroup$ Noted. Thanks... $\endgroup$
    – gete
    Sep 20 '19 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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