کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649804 | 1342467 | 2009 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: ββ-degree closures for graphs ββ-degree closures for graphs](/preview/png/4649804.png)
Bondy and Chvátal [J.A. Bondy, V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111–135] 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 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. In this paper we show that the condition d(a)+d(b)≥kd(a)+d(b)≥k can be replaced by a much better one: 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.
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 2968–2973