I am reading "Intersection Graphs" from chapter 2 in Frank Harary Graph Theory Book
Let $S$ be a set and $F=\{S_1,\ldots,S_p\}$ a nonempty family of distinct nonempty subsets of $S$ whose union is $S$. The intersection graph of $F$ is denoted $\Omega(F)$ and defined by $V(\Omega(F))=F$, with $S_i$ and $S_j$ adjacent whenever $i\neq j$ and $S_i\cap S_j\neq\emptyset$. Then a graph $G$ is an intersection graph on $S$ if there exists a family $F$ of subsets of $S$ for which $G$ and $\Omega(F)$ are isomorphic graphs.
Now, coming to my questions:
-
What is the set S in this context? Since we are talking about graphs is it "$S = ( V, E )$", where $V$ and $E$ themselves are sets?
-
Or is $S$ a set of all vertices and edges in a graph.
In either of the case, it does not make sense, cause the number of subsets, which I believe here mean a vertex in the resultant graph, would be more than the total vertex in the original graph and then the original and the resultant graph won't be isomorphic.
Best Answer
In general, the set $S$ can be anything you like, and the set $F$ can be any family of subsets of $S$ you like. There's no question of the "original graph" and "resultant graph" being isomorphic, because you're not necessarily starting with any "original graph": you are constructing a graph $\Omega(F)$ out of the information in $F$.
For example, suppose I am a big fan of the set family $\{\{1,2,3\}, \{2,3,4\}, \{3,4,5\}, \{4,5,6\}\}$. Then I could create the intersection graph $\Omega(\{\{1,2,3\}, \{2,3,4\}, \{3,4,5\}, \{4,5,6\}\})$, which would look like this:
Further, we say that a graph $G$ is an intersection graph on $S$ if $G$ is isomorphic to $\Omega(F)$ for some $F$ that's a family of subsets of $S$. The diagram above shows that if you delete an edge from $K_4$ and call that $G$, then $G$ is an intersection graph on $\{1,2,3,4,5,6\}$.
When you're figuring out if we can represent a graph as an intersection graph, then we have a question of an "original graph" $G$ which we're comparing to $\Omega(F)$. But we're still not told what $S$ must be. We must pick $S$ and $F$ ourselves in some clever way that makes $\Omega(F)$ isomorphic to $G$.
For example, we can prove (and I think Harary does this) that every graph $G$ is an intersection graph on $E(G)$: the set of all edges in $G$. Specifically:
Then $\Omega(F)$ is isomorphic to $G$.
Some special families of graphs also have other representations as intersection graphs, with a different $S$ and $F$.