The closure of a graph $G$, denoted $cl(G)$ is defined to be the supergraph of $G$ obtained from $G$ by recursively joining pairs of nonadjecent vertices whose degree sum is atleast $n$ untill no such pair exists.[n=|V(G)|]

Here if we add edges to non agecent vertices with $d_G(u)+d(v)\ge n$, adding edge $uv$ means $d_{G+uv}(u)+d_{G+uv}(v)=d_G(u)+1+d_G(v)+1\ge n+2 > n$ still the degree sum is more than n. Can you please help me to understand the definition?

  • $\begingroup$ Can you please proofread and edit your question? (You can click on "edit" just beneath the question itself.) It contains some non-words (like "ning" and "verof") and some things that are clearly typos. It's also not at all clear what $n$ denotes in your definition of closure -- can you please explain? $\endgroup$ – John Hughes Oct 4 '18 at 15:16
  • 1
    $\begingroup$ The definition is right. (See J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math., 15 (1976), pp. 111-135.) Note that the procedure only adds edges between nonadjacent vertices. On a finite graph it must terminate. $\endgroup$ – Fabio Somenzi Oct 4 '18 at 15:28
  • 1
    $\begingroup$ It doesn't have to terminate with a complete graph, but it well may. If the result is $K_n$, it follows from a theorem in O. Ore, Note on Hamilton Circuits, Am. Math. Monthly, 67 (1960) 55 that the original graph is Hamiltonian. In fact if the result is Hamiltonian, so is the original graph. $\endgroup$ – Fabio Somenzi Oct 4 '18 at 15:38
  • 1
    $\begingroup$ Yes, I got a graph whose degree sum is <n for any pair on non adjecent vertices.here, I guess $cl(G)=G$. right? $\endgroup$ – Math geek Oct 4 '18 at 15:52
  • 1
    $\begingroup$ @Mathgeek Yes, in that case no edge is added and the procedures immediately returns $G$. $\endgroup$ – Fabio Somenzi Oct 4 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.