# Alpha-Degree Closures for Graphs

*Ahmed Ainouche*

Additional contact information

Ahmed Ainouche: CEREGMIA, UniversitÃ© des Antilles et de la Guyane

No 2011-06, Documents de Travail from CEREGMIA, Université des Antilles et de la Guyane

**Abstract:**
Bondy and Chvatal [7] introduced a general and unified approach to a variety of graph-theoretic problems. They defined the k-closure Ck(G), where k is a positive integer, of a graph G of order n as the graph obtained from G by recursively joining pairs of nonadjacent vertices a,b satisfying the condition C(a,b): d(a) + d(b) >= k. From many properties P, they found a suitable k (depending on P and n) such that Ck(G) has property P if and only if G does. For instance, if P is the hamiltonian property, then k=n. In [3], we proved that C(a,b) can be replaced by d(a) + d(b) + |Q(G)| >= k, where Q(G) is a well-defined subset of vertices nonadjacent to a,b. In [4], we proved that, for a (2+k-n)-connected graph, C(a,b) can be replaced by |N(a) U N(b)| + d_ab + e_ab >= k, where e_ab is a well-defined binary variable and d_ab is the minimum degree over all vertices distinct from a,b and non adjacent to them. The condition on connectivity is a necessary one. In this paper, we show that C(a,b) can be replaced by the condition d(a) + d(b) (Ã¢_ab - a_ab) >= k, where Ã¢_ab and a_ab are respectively the order and independence number of the subgraph G - N(a) U N(b).

**Keywords:** closure; degree closure; neighborhood closure; dual closure; stability; hamiltonicity; cyclability; degree sequence; matching number; k-leaf-connected (search for similar items in EconPapers)

**Pages:** 12 pages

**Date:** 2011-12

**References:** Add references at CitEc

**Citations:**

**Downloads:** (external link)

http://www2.univ-ag.fr/RePEc/DT/DT2011-06_Ainouche.pdf First version, 2011 (application/pdf)

**Our link check indicates that this URL is bad, the error code is: 404 Not Found**

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:crg:wpaper:dt2011-06

Access Statistics for this paper

More papers in Documents de Travail from CEREGMIA, Université des Antilles et de la Guyane Contact information at EDIRC.

Bibliographic data for series maintained by Janis Hilaricus ().