کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650468 1342488 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Häggkvist conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Häggkvist conjecture
چکیده انگلیسی

In this paper, by using minimum out-degree and minimum in-degree, we give a new lower bound on the vertex-strong connectivity of an oriented graph. In the case of a tournament, our lower bound improves that of Thomassen obtained in 1980 and which use the notion of irregularity (see [C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163]). As application, we determine a pertinent upper bound on the diameter of some oriented graphs, and in a particular case, related to Caccetta Häggkvist conjecture, we improve a result of Broersma and Li obtained in 2002 (see [H.J. Broersma, X. Li, Some approaches to a conjecture on short cycles in digraphs, Discrete Appl. Math. 120 (2002) 45–53]).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 22, 28 November 2008, Pages 5274–5279
نویسندگان
,