6
$\begingroup$

A sequence of integers $d_1, \dots, d_n$ is called graphical if there exists a simple graph $G$ with it as its degree sequence. Deciding if a sequence is graphical is called the Graph Realization Problem.

A theorem by Havel and Hakimi gives an algorithm to construct such a graph if it exists: it proceeds by repeatedly selecting a vertex of highest degree $v$ and connecting it to vertices of high degree until the degree of $v$ is depleted.

I want instead to consider the algorithm that, at every step, connects a vertex of highest degree with a single vertex of lowest nonzero degree. Note that this algorithm, unlike the Havel-Hakimi one, does not select a vertex of the highest degree and connects it until its degree is depleted: a new vertex of highest degree is selected every time an edge is added.

For example, given the graphical degree sequence $2, 2, 2, 1, 1$, the algorithm proceeds as follows:

$$1,2,2,0,1\\0,1,2,0,1\\0,0,1,0,1\\0,0,0,0,0$$

which yields the simple path $P_5$ on five vertices (where I broke the ties selecting the leftmost highest or smallest).

Is there a counterexample for which this algorithm does not yield a graph realization?

NOTE: I expect the answer to be affirmative, since this algorithm won't ever connect two vertices of low degree unless it depleted everything else. Therefore, if any graph realization of a certain degree sequence must contain an edge between two vertices of low degree we're done, but I wasn't able to find such an example.

$\endgroup$
  • $\begingroup$ According to the wikipedia page you linked the algorithm will always produce a realization if one exists. Are you looking for specific sequences that are not graphical? $\endgroup$ – Jorik Dec 14 '15 at 16:29
  • $\begingroup$ Apologies for the confusion: I'm not asking about the Havel-Hakimi algorithm, but for the algorithm below (the one connecting a vertex of highest degree with a vertex of lowest degree). $\endgroup$ – Jacopo Notarstefano Dec 14 '15 at 16:43
  • $\begingroup$ Ah, I misread the question. My apologies. I'll think about it a little. $\endgroup$ – Jorik Dec 14 '15 at 16:46
  • $\begingroup$ Jacopo-- If you previously looked at my answer, I deleted it because I didn't think I had understood the algorithm. Please have a look at the answer now, which has been re-written. $\endgroup$ – coffeemath Dec 14 '15 at 22:29
  • $\begingroup$ Apologies for your misunderstanding as well — hopefully the edit I just made will clarify the point you raised in your answer. $\endgroup$ – Jacopo Notarstefano Dec 15 '15 at 1:08
4
$\begingroup$

There are some problems with your algorithm:

1)

It fails to distinguish solvable from unsolvable positions: If given a sequence such as nn it will happily go along adding edges between the two. This leads into

2)

Your algorithm doesn't produce simple graphs regardless of tiebreakers:

consider the sequence 64332222. this has a realization (just draw it). However, regardless of tiebreakers, your algorithm will always try to connect the first vertex to one of the 2s twice. This is one of the big upsides of havel-hakimi, by instantly depleting the degree of nodes when adding edges to them they don't run into the problem of multiedges.

If you were to restrict your algorithm to only connect unconnected edges it would likely produce valid realizations. However, that'd come at the cost of having to pass way more information along than the list of (unused) degree of each vertex. I think your algorithm will produce valid realizations because if you have a realization where there is an edge between vertices, say ab and cd and none between ac and bd then you may remove ab,cd and add ac,bd to produce another realization of the same sequence. In this way it should be possible to always avoid/force edges between vertexes of high and low degree.

$\endgroup$
  • $\begingroup$ Ah, yes, the argument in 1. clearly implies that the algorithm is underspecified and requires an additional data structure to keep track of the edges. I also like the argument in 2. to show that the Havel-Hakimi strategy and the other one are roughly "dual", which is why I was having trouble finding a counterexample. I will keep the question open a few more days in case someone manages to find one, though. $\endgroup$ – Jacopo Notarstefano Dec 16 '15 at 22:50
  • $\begingroup$ As noted above, this answers the question as written, but only sketches an argument for why the algorithm appears to work in practice (provided one also keeps track of the edges). I won't probably ask a followup question on that, but I welcome anyone to do so! $\endgroup$ – Jacopo Notarstefano Dec 19 '15 at 15:59

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.