Suppose G is a graph on n vertices. Then the closure of G, written [G], is constructed by adding edges that connect pairs of non-adjacent vertices u and v for which

$\deg(u) + \deg(v) \geq n.$

One continues recursively, adding new edges until all non-adjacent pairs u, v satisfy

$\deg(u) + \deg(v) < n.$

Is it unique for a graph?

  • 2
    $\begingroup$ Maybe I am missing something, but if you are adding edges, you can only increase the degrees. Is the second inequality meant to be $\deg(u)+\deg(v)\ge n$ and the first one $\deg(u)+\deg(v)<n$? $\endgroup$ – Martin Sleziak Apr 28 at 5:15
  • $\begingroup$ It is also unclear to me from your description whether in one step of the algorithm you just add one edge (for some vertices that satisfy the requirements), or whether you join all pairs of vertices fulfilling the conditions on degrees. $\endgroup$ – Martin Sleziak Apr 28 at 5:19
  • $\begingroup$ @MartinSleziak We add one edge for each step of the algorithm. Also, if we add an edge between non-adjacend vertices, they became adjacend, so their degrees are nor satisfy the requirements since the vertices became adjacent. $\endgroup$ – ardlen Apr 28 at 5:24
  • 1
    $\begingroup$ AFAICT, the final result is going to be the same as iterating construction of creating from the graph $G$ a new graph $G'$, where an edge is added all pairs with $\deg_G(u)+\deg_G(v)\ge n$. If you describe the construction in this way, it should be clear that the final result is uniquely determined. $\endgroup$ – Martin Sleziak Apr 28 at 5:48
  • 1
    $\begingroup$ @GerhardPaseman A graph is hamiltonian iff its closure is hamiltonian. $\endgroup$ – Bullet51 Apr 28 at 6:13

Many years ago Staszek Radziszowski and I published a very elementary lemma that covers this case and many similar cases.

Let $(X,\le)$ be a partially ordered set and let $\varPhi$ be a family of functions from $X$ to $X$. Suppose that, for $x,x'\in X$ and $\phi\in\varPhi$ we have $\phi(x)\le x$ and $x\le x'\implies \phi(x)\le\phi(x')$. Call $x\in X$ $\varPhi$-stable if $\phi(x)=x$ for all $\phi\in\varPhi$. Let $\varPhi^*(x)$ be the closure of $\lbrace x\rbrace$ under $\varPhi$.

Lemma. For each $x\in X$, $\varPhi^*(x)$ contains at most one $\varPhi$-stable element.

To apply it to this case, $X$ is the set of all (labelled) graphs on $n$ vertices and $x\le x'$ means that $x$ is a super-graph of $x'$. There is a function for each pair of vertices $i,j$ which makes them adjacent if their degree sum is at least $n$ and does nothing otherwise. There is at least one $\varPhi$-stable graph (add edges until you can't add more) so by the lemma it is unique.

See Lemma 2 of this paper.


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.