αα-degree closures for graphs

Bondy and Chvátal (1976) [7] introduced a general and unified approach to a variety of graph-theoretic problems. They defined the kk-closure Ck(G)Ck(G), where kk is a positive integer, of a graph GG of order nn as the graph obtained from GG by recursively joining pairs of nonadjacent vertices a,ba,b satisfying the condition C(a,b)C(a,b): d(a)+d(b)≥kd(a)+d(b)≥k. For many properties PP, they found a suitable kk (depending on PP and nn) such that Ck(G)Ck(G) has property PP if and only if GG does. For instance, if PP is the Hamiltonian property, then k=nk=n.In Ainouche and Christofides (1987) [5], we proved that C(a,b)C(a,b) can be replaced by d(a)+d(b)+|Q(G)|≥kd(a)+d(b)+|Q(G)|≥k, where Q(G)Q(G) is a well-defined subset of vertices nonadjacent to a,ba,b.In Ainouche and Christofides (1981) [4], we proved that, for a (2+k−n)(2+k−n)-connected graph, C(a,b)C(a,b) can be replaced by |N(a)∪N(b)|+δab+εab≥k|N(a)∪N(b)|+δab+εab≥k, where εabεab is a well-defined binary variable and δabis the minimum degree over all vertices distinct from a,ba,b and nonadjacent to them. The condition on connectivity is a necessary one.In this paper we show that C(a,b)C(a,b) can be replaced by the condition d(a)+d(b)+(α¯ab−αab)≥k, where α¯aband αabαab are respectively the order and the independence number of the subgraph G−N(a)∪N(b)G−N(a)∪N(b).These last three conditions are all uncomparable, unique and well-defined. Moreover any Hamiltonian cycle in Cn(G)Cn(G) can be transformed into a Hamiltonian cycle in the original graph within a polynomial time. However, unlike the conditions given in Ainouche (in preparation) [3] and Ainouche and Christofides (1981) [4], the condition (α¯ab−αab) cannot be computed in polynomial time. By giving suitable upper bounds of αabαab (or lower bounds of (α¯ab−αabt)) we satisfy this last nice property. In doing so, we surprisingly obtain a result of Broersma and Schiermeyer (1994) [9] as an easy corollary.