Alpha-Degree Closures for Graphs
Ahmed Ainouche · RePEc: Research Papers in Economics · 2011
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).