کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648702 1342426 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on an embedding problem in transitive tournaments
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A note on an embedding problem in transitive tournaments
چکیده انگلیسی

Let TTnTTn be a transitive tournament on nn vertices. It is known Görlich, Pilśniak, Woźniak, (2006) [3] that for any acyclic oriented graph G⃗ of order nn and size not greater than 34(n−1), two graphs isomorphic to G⃗ are arc-disjoint subgraphs of TTnTTn. In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph G⃗ of size at most 23(n−1) is embeddable into all its complements in TTnTTn. Moreover, this bound is generally the best possible.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 4, 28 February 2010, Pages 681–686
نویسندگان
, ,