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 ().