کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902952 1632397 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A study on oriented relative clique number
ترجمه فارسی عنوان
یک مطالعه بر روی تعداد ارقام نسبی ارقام
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An oriented graph is a directed graph with no directed cycle of length one or two. The relative clique number of an oriented graph is the cardinality of a largest subset X of vertices such that each pair of vertices is either adjacent or connected by a directed 2-path. It is known that the oriented relative clique number of a planar graph is at most 80. Here we improve the upper bound to 32. We also prove an upper bound of 14 for oriented relative clique number of triangle-free planar graphs. Furthermore, we determine the exact values of oriented relative clique number for the families of outerplanar graphs with girth at least g and planar graphs with girth at least g+2 for all g≥3. Moreover, we study the relation of oriented relative clique number with oriented chromatic number, oriented absolute clique number and maximum degree of a graph. We also show that oriented relative clique number of a connected subcubic graph is at most seven which weakly supports a conjecture by Sopena (JGT 1997).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 7, July 2018, Pages 2049-2057
نویسندگان
, , ,