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

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
نویسندگان
, , ,