کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871142 | 1440178 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
ترجمه فارسی عنوان
غربالگری و ارزیابی مرتب سازی برخی از کلاسهای بیوگرافی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Chordal graphs, permutation graphs, and interval graphs are among many classes of graphs which can be characterized by the existence of certain acyclic orientations and vertex orderings. These types of characterizations exist for some of their bipartite analogues such as chordal bipartite graphs and bipartite permutation graphs. Chvátal proved that a bipartite graph G is chordal bipartite if and only if the complement G¯ of G has a vertex ordering ⺠such that for every induced path abcd in G¯, aâºb implies câºd. Recently, Le proved that a bipartite graph G is a permutation graph if and only if G¯ admits an acyclic orientation such that for every induced path abcd in G¯, ab is an oriented edge if and only if cd is. Interestingly these orientation and vertex ordering characterizations are stated on the complements of bipartite graphs. We show that interval bigraphs and interval containment bigraphs also admit similar characterizations in terms of vertex orderings and acyclic orientations of their complements.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 190-193
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 190-193
نویسندگان
Jing Huang,