3
$\begingroup$

I'm currently starting a course about Graph Theory, and I've been explained about the Havel & Hakimi degree sequence. However, I'm not too sure about it yet. First of all, I want to know if I understand it correctly, so I'm going to try to explain what I think the theory proves.

First, I've shamelessly stolen the following statement from the presentation:

enter image description here

Okay, so what I want to ask is the following.

  1. What does "is graphic" mean exactly. Does that mean it's a graph? I know stupid question, but I cannot think of a degree sequence that's not a graph...

  2. What's the practical use of this. What problems could you solve with this.

$\endgroup$
  • $\begingroup$ From degrees you can tell if the graph is Eulerian, you can tell if graph is a tree $\endgroup$ – Yaroslav Bulatov Feb 3 '11 at 19:12
6
$\begingroup$
  1. I think the term is usually "graphical." It just means that $s^{*}$ is a sequence of degrees of the vertices of some graph $G$. So if you can create a graph with degrees from $s^{*}$ then you can create a graph with degrees from $s$ and vice versa. Note it doesn't mean that you create the same graph from $s$ and $s^{*}$. We just need to be able to create graphs from the sets of degrees (e.g. if $s$ is graphical, then we can create a graph $G$ from $s$ and a graph $G'$ from $s^{*}$).

  2. It can be used to figure out whether two graphs are isomorphic. If the degree sequences of two graphs are different, then they can't be isomorphic.

$\endgroup$
  • $\begingroup$ I believe 2 isn't about degree sequences, but about Havel-Hakimi. $\endgroup$ – Aryabhata Feb 3 '11 at 17:25
3
$\begingroup$

There is a nice treatment of the Havel-Hakimi theorem on pages 44-46 of Doug West's book, Introduction to Graph Theory (Second edition). As far as uses of this kind of result one might be using graph theory to model some physical molecule that one would want to construct. One first step might be to see if there is a graph with specified valences (degrees). Often one wants a graph with the specified valences and additional properties such as that the graph with these valences is a tree or can be embedded in the plane where the edges meet only at vertices. Many additional specialized results about "realizing" graphs with specific properties and specified valences have been found.

$\endgroup$
0
$\begingroup$
  1. Graphic Sequence is only for simple graphs. It means that if a degree sequence is also a graphic sequence, the graph is simple.

  2. If you prove that a huge graph is a simple graph (using Havel & Hakimi) you can use the properties of simple graphs to select best algorithms to solve further problems on mentioned graph.

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