کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9516050 | 1343756 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rank-width and vertex-minors
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The rank-width is a graph parameter related in terms of fixed functions to clique-width but more tractable. Clique-width has nice algorithmic properties, but no good “minor” relation is known analogous to graph minor embedding for tree-width. In this paper, we discuss the vertex-minor relation of graphs and its connection with rank-width. We prove a relationship between vertex-minors of bipartite graphs and minors of binary matroids, and as an application, we prove that bipartite graphs of sufficiently large rank-width contain certain bipartite graphs as vertex-minors. The main theorem of this paper is that for fixed k, there is a finite list of graphs such that a graph G has rank-width at most k if and only if no graph in the list is isomorphic to a vertex-minor of G. Furthermore, we prove that a graph has rank-width at most 1 if and only if it is distance-hereditary.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 95, Issue 1, September 2005, Pages 79-100
Journal: Journal of Combinatorial Theory, Series B - Volume 95, Issue 1, September 2005, Pages 79-100
نویسندگان
Sang-il Oum,