0
$\begingroup$

I have a graph $G(V, E)$. I want to know the number of unique subgraphs with diameter d >= 1. I will give a couple of examples:

1) In the following graph, there is 3 unique subgraphs of diameter 1.

enter image description here

2) In this one, although it contains 3 vertices like the first one, has a single subgraph of diameter 1. (itself)

enter image description here

3) In this one, there is 3 of diameter 1.

enter image description here

Maybe I can explain my problem algorithmically, since I am not a mathematician and researching the problem did not help.

For every vertex $v \in G(V)$, get the subgraph containing $v$ such as the distance from $v$ to every other vertex in the subgraph is less than or equal to $d$. So what I want is not how to get all subgraphs, but the count of subgraphs. (Well if there is an answer for how to get them in an efficient way I don't mind it as a bonus).

$\endgroup$
  • $\begingroup$ I am sorry maybe I used the term diameter in a wrong way :/ But I think the algorithmic explanation is clear $\endgroup$ – FearUs Sep 12 '13 at 2:16
  • $\begingroup$ Why it's not 4 for the second case? I don't understand why you don't consider the 3 sub graph containing each one edge ... $\endgroup$ – wece Sep 12 '13 at 14:03
  • $\begingroup$ Because if you apply the algorithmic description, you get the following: Select v = north vertex. Add it to the new subgraph. Look for all vertices w in the graph where dist(v,w) = 1 (if d > 1, then 1<= dist(v,w) <= d, add them (with their edges) to the new subgraph. You will get the complete graph in that case. In fact whatever vertice you start with you will end with the complete graph. $\endgroup$ – FearUs Sep 12 '13 at 23:38
0
$\begingroup$

It seems the following.

If I understood you right, then if we have a graph $G$ we can calculate the number of its unique subgraphs with diameter $d\ge 1$ as follows. Put $n=|V|$, enumerate the vertices of the graph $G$ as $v_1,\dots, v_n$ and determine its adjacency $n\times n$ boolean matrix $M=\|m_{ij}\|$ as $m_{ij}=1$ iff $i=j$ or the vertices $v_i$ and $v_j$ are joined by an edge (and $m_{ij}=1$ in the opposite case). Then for each $v_i$, $v_j$ and each positive integer $d$ we have that the edge distance between the vertices $v_i$ and $v_j$ is not greater than $d$ iff $m_{ij}^d=1$, where $m_{ij}^d$ is an $ij$-th element of the boolean $d$-th power $m^d$ of the matrix $M$ (that is, while calculating this power we multiply matrices as usual, but take $”\vee”$ instead of $”+”$ and $”\&”$ instead of $”\cdot”$). Now the number of unique subgraphs of $G$ with diameter $d$ is equal to the number of different rows of the matrix $M^d$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.