0
$\begingroup$

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.

$\endgroup$

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.