1
$\begingroup$

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$

No:of elements in $V(G)$ with degree $i $ = No:of elements in $V(H)$ with degree $i$

Where $V(G)$ is the vertex set of $G$.

Given this can we say that $H$ and $G$ are isomorphic?

If they are not isomorphic. Then what is such a relation called?

$\endgroup$
  • $\begingroup$ If there are $N$ vertices there can only be a maximum degree of $N-1$. $\endgroup$ – biryani Nov 4 '14 at 15:06
  • 1
    $\begingroup$ @LeenDroogendijk: Note that since the number of vertices in $G,H$ is the same, it suffices to check that they have equal numbers of vertices with degrees $i=1,\ldots,N-1$ to prove the same degree sequences (equal numbers of isolated vertices is then forced). $\endgroup$ – hardmath Dec 3 '14 at 2:59
2
$\begingroup$

The two graphs $G$ and $H$ satisfying the condition you describe are said to have the same degree sequence. But this does not necessarily imply that the two graphs are isomorphic. It is possible to construct two graphs that have the same degree sequence but which are not isomorphic.

There is no known list of graph properties (be it the degree sequence, any other graph invariant, or even a combined list of such invariants) that provides a sufficient condition for two given graphs to be 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.