4
$\begingroup$

The similarity between two undirected graphs $G_1$ and $G_2$ that have the same $n$ vertices can be defined using:

$$ S(G_1,G_2) = \frac {\sum_i\min(\deg(v_i \in G_1), \deg(v_i \in G_2))} {2 \times \max(|G_1|,|G_2|)} $$

where $\deg(v \in G)$ indicates the degree of a vertex $v$ in graph $G$ and $|G|$ indicates the number of edges in $G$. If $S(G_1, G_2) = 1$, are the two graphs equivalent?

$\endgroup$
  • 3
    $\begingroup$ Is there some standard metric for similarity you are referring to? Can you provide a definition and/or reference? $\endgroup$ – GeoMatt22 Sep 26 '16 at 2:17
  • $\begingroup$ Similarity of two undirected graphs having the same n vertices is 1 $\endgroup$ – Mk47 Sep 26 '16 at 4:01
  • $\begingroup$ If that is the definition, then you would seem to have answered your own question? However your statement seems like an odd definition of graph similarity, when it only has to do with vertex sets. Typically a graph would be defined as $\{E,V\}$, which includes both a vertex set $V$ as well as an edge-set $E\subset V\times V$ (at a minimum, i.e. for an unweighted graph). $\endgroup$ – GeoMatt22 Sep 26 '16 at 14:03
3
$\begingroup$

Unfortunately, graph isomorphism is a harder problem then just matching vertex degrees, as this figure demonstrates.

Figure

Both are undirected graphs on the same six vertices, labeled "1" through "6". The vertex degrees on both are the same, vertex by vertex: one vertex ("1") has degree 5, two ("3" and "6") have degree 2, and three have degree 3. Therefore your similarity metric equals $1$.

Note, however, that the three degree-3 vertices (labeled "2", "4", and "5") form a triangle at the left but not at the right. Therefore the two graphs are not isomorphic.

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