کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420418 | 683934 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Full orientability of graphs with at most one dependent arc
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Suppose that DD is an acyclic orientation of a graph GG. An arc of DD is dependent if its reversal creates a directed cycle. Let dmin(G) (dmax(G)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of GG. We call GGfully orientable if GG has an acyclic orientation with exactly dd dependent arcs for every dd satisfying dmin(G)⩽d⩽dmax(G). We show that a connected graph GG is fully orientable if dmin(G)⩽1. This generalizes the main result in Fisher et al. [D.C. Fisher, K. Fraughnaugh, L. Langley, D.B. West, The number of dependent arcs in an acyclic orientation, J. Combin. Theory Ser. B 71 (1997) 73–78].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 13, 6 July 2009, Pages 2969–2972
Journal: Discrete Applied Mathematics - Volume 157, Issue 13, 6 July 2009, Pages 2969–2972
نویسندگان
Hsin-Hao Lai, Ko-Wei Lih, Li-Da Tong,