کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648433 | 1342411 | 2010 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Traceability of kk-traceable oriented graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Traceability of kk-traceable oriented graphs Traceability of kk-traceable oriented graphs](/preview/png/4648433.png)
چکیده انگلیسی
A digraph of order at least kk is kk-traceable if each of its subdigraphs of order kk is traceable. We note that 2-traceable oriented graphs are tournaments and for k≥3k≥3, kk-traceable oriented graphs can be regarded as generalized tournaments. We show that for 2≤k≤62≤k≤6 every kk-traceable oriented graph is traceable, thus extending the well-known fact that every tournament is traceable. This result does not extend to k=7k=7. In fact, for every k≥7k≥7, except possibly for k=8k=8 or 10, there exist kk-traceable oriented graphs that are nontraceable. However, we show that for every k≥2k≥2 there exists a smallest integer t(k)t(k) such that every kk-traceable oriented graph of order at least t(k)t(k) is traceable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 8, 28 April 2010, Pages 1325–1333
Journal: Discrete Mathematics - Volume 310, Issue 8, 28 April 2010, Pages 1325–1333
نویسندگان
Susan A. van Aardt, Jean E. Dunbar, Marietjie Frick, Peter Katrenič, Morten H. Nielsen, Ortrud R. Oellermann,