Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649803 | Discrete Mathematics | 2009 | 7 Pages |
Abstract
For any positive integer kk and any (2+k−n)(2+k−n)-connected graph of order nn, we define, following Bondy and Chvatàl, the kk-neighborhood closure NCk(G)NCk(G) as the graph obtained from GG by recursively joining pairs of nonadjacent vertices a,ba,b satisfying the condition |N(a)∪N(b)|+δab+εab≥k|N(a)∪N(b)|+δab+εab≥k, where δab=min{d(x)|a,b∉N(x)∪{x}}δab=min{d(x)|a,b∉N(x)∪{x}} and εabεab is a well defined binary variable. For many properties PP of GG, there exists a suitable kk (depending on PP and nn) such that NCk(G)NCk(G) has property PP if and only if GG does.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ahmed Ainouche,