کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5776927 1413645 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
1-perfectly orientable graphs and graph products
ترجمه فارسی عنوان
نمودارها و محصولات گراف کاملا متحرک
کلمات کلیدی
گراف کاملا 1 جهتدار گراف ارادۀ برادرانه، هارف در مسابقات ضرب دکارتی، محصول مستقیم، محصول قوی، محصول واژگونی نمودار زنجیره ای، مشخصات ساختاری،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A graph G is said to be 1-perfectly orientable (1-p.o. for short) if it admits an orientation such that the out-neighborhood of every vertex is a clique in G. The class of 1-p.o. graphs forms a common generalization of the classes of chordal and circular arc graphs. Even though 1-p.o. graphs can be recognized in polynomial time, no structural characterization of 1-p.o. graphs is known. In this paper we consider the four standard graph products: the Cartesian product, the strong product, the direct product, and the lexicographic product. For each of them, we characterize when a nontrivial product of two graphs is 1-p.o.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1727-1737
نویسندگان
, ,