Graph Question problem For a graph $G$ and $i \in N$, we define $G_i$ as a graph with the same vertex set as $G$, and where
any pair of vertices $u$ and $v$ have an edge between them in $G_i$ if and only if there is a path from $u$ to $v$ in
the original graph $G$ of length less than or equal to $i$. Clearly, $G_1$ is equal to $G$.


*

*Find the number of non-isomorphic graphs $G$ on $n$ nodes, such that $G = G_2$.

*Find the number of "labeled graphs" $G$ on $n$ nodes, such that $G = G_2$. (Since you are asked to count labeled graphs, count 2 isomorphic graphs as different!)
Any hints on how to go about solving this
 A: Your $G_2$ is usually called $G^2,$ the square of the graph $G.$ If $G^2=G$ then, by induction, two vertices of $G$ which are connected by a path of any length are joined by an edge; in other words, the connected components of $G$ are complete graphs; in still other words, $G$ is a sum of complete graphs. Let me call such a graph "idempotent".
The number of nonisomorphic idempotent graphs of order $n$ is the partition number $p(n),$ the number of partitions of the number $n;$ this is OEIS sequence A000041.
The number of labeled idempotent graphs of order $n$ is the Bell number $B_n,$ the number of partitions of the set $[n]=\{1,2,\dots,n\};$ this is OEIS sequence A000110.
A: Here's what I came up with:
A graph $G$ will be the same as its $G_{2}$ only if for all $u$ and $v$ of $G$, there is an edge between $u$ and $v$ iff there is a path of length two between $u$ and $v$.
Trivially, all edgeless graphs satisfy this property. And also note that the smallest not-so-trivial graph with this property is $K_{3}$.
Now, say we start from the edgeless graph on $n$ vertices $E_{n}$, and want to add edges to it while conserving this property. Pick any two vertices $u$ and $v$. If we are to add an edge between them, then we also must add edges $uw$ and $vw$, for some other vertex $w$, to form the triangle.
So, starting from $E_{n}$, constructing a graph with the desired property is merely picking $3$-subsets of its vertex set and letting those form a triangle. Clearly there are $\binom{n}{3}$ possible first choices, and, as we can keep iterating this construction step, counting the edgeless graph as "zero steps", there are $2^{\binom{n}{3}}$ graphs on $n$ vertices with the property in question.
After that, we only need to settle the isomorphism matter and perhaps verify if indeed the graphs constructed as above are the only ones with the desired property - its converse we already know.
