کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872221 681647 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On opposition graphs, coalition graphs, and bipartite permutation graphs
ترجمه فارسی عنوان
در نمودارهای مخالف، نمودارهای ائتلافی و نمودارهای جایگذاری دو طرفه
کلمات کلیدی
نمودار کاملا قابل سفارش نمودار یک در یک، نمودار تعویض دو طرفه، نمودار اپوزیسیون گراف ائتلاف،
ترجمه چکیده
یک گراف یک نمودار مخالف است، به ترتیب یک گراف ائتلافی، اگر آن را پذیرش یک جهت تقریبی است که به دو جهت در هر جهت، دو لبه انتهایی هر مسیر چهارطرفه بدون درهم و برهم در مخالفت قرار می گیرد. نمودارهای اپوزیسیون و ائتلافی در ارتباط با نمودارهای کامل معرفی و بررسی شده است. تشخیص و مشخص کردن نمودارهای مخالفان و ائتلاف همچنان با مشکلاتی روبرو هستیم. در این مقاله، مشخصه هایی برای نمودارهای مخالف دو طرفه و نمودارهای ائتلاف دو طرفه و برای نمودارهای مخالف دو طرفه ارائه می شود. الگوریتم تشخیص خطی برای این نمودارها به صورت ذاتی در استدلال ما است. به عنوان یک محصول جالب توجه، ما ویژگی های زیرمتریزه جدید را برای نمودارهای تعویض دو طرفه مورد مطالعه قرار می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
در نمودارهای مخالف، نمودارهای ائتلافی و نمودارهای جایگذاری دو طرفه
چکیده انگلیسی
A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs still remain long-standing open problems. The present paper gives characterizations for co-bipartite opposition graphs and co-bipartite coalition graphs, and for bipartite opposition graphs. Implicit in our argument is a linear time recognition algorithm for these graphs. As an interesting by-product, we find new submatrix characterizations for the well-studied bipartite permutation graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 26-33
نویسندگان
,