Question about Intersection Graph in Graph Theory

graph theoryset-theory

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:

  1. 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?

  2. 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:

enter image description here

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:

  • Let $S = E(G)$;
  • For every vertex $v \in V(G)$, let $S_v$ be the subset of all edges incident to $v$;
  • Let $F = \{S_v : v \in V(G)\}$.

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$.

Related Question