Let us have a set of nodes $V$, such that $|V|=N$. Let $G= (V,E)$ be an arbitrary directed graph on $V$. Let $U$ be the set of all possible directed graphs on $V$.Hence, $|U| = 2^{|V|^2}$. Now, for a given directed graph $G$, we define $G[k]$ as the set of all $k$-subgraphs on $G$. Hence, for any $G$, $|G[k]| = \binom{|V|}{k} $. Now, let $O_{k}$ be the set of all possible $k$-sized directed graphs, then all the k-subgraphs in $G[k]$ must be isomorphic to one of the elements of $O_k$, which has a size $2^{k^2}$.

For any graph $G$ let $G(k) = <a_1,a_2...a_{2^{k^2}}>$ be a vector, such that $a_i$ is the number of k-subgraph in $G$ which are isomorphic to the $i^{th}$ element in $O_{k}$. What is the most efficient way of finding the number of $G's$ that share the same $G(k)$ ?

PS: The number of $G's$ counts isomorphic graphs distinctly.


Your Answer

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

Browse other questions tagged or ask your own question.