کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648376 | 1632438 | 2010 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Absolute retracts and varieties generated by chordal graphs Absolute retracts and varieties generated by chordal graphs](/preview/png/4648376.png)
Graphs that are retracts of each supergraph in which they are isometric are called absolute retracts with respect to isometry, and their structure is well understood; for instance, in terms of building blocks (paths) and operations (products and retractions). We investigate the larger class of graphs that are retracts of each supergraph in which all of their holes are left unfilled. These are the absolute retracts with respect to holes, and we investigate their structure in terms of the same operations of products and retractions. We focus on a particular kind of hole (called a stretched hole), and describe a class of simple building blocks of the corresponding absolute retracts. Surprisingly, these also turn out to be precisely those absolute retracts that can be built from chordal graphs. Monophonic convexity is used to analyse holes on chordal graphs.
Journal: Discrete Mathematics - Volume 310, Issues 10–11, 6 June 2010, Pages 1507–1519