کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9506023 1340371 2005 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Families of matroids induced by classes of graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Families of matroids induced by classes of graphs
چکیده انگلیسی
It is easily proved that, if P is a class of graphs that is closed under induced subgraphs, then the family of matroids whose basis graphs belong to P is closed under minors. We give simple necessary and sufficient conditions for a minor-closed class of matroids to be induced in this way, and characterise when such a class of matroids contains arbitrarily large connected matroids. We show that five easily-defined families of matroids can be induced by a class of graphs in this manner: binary matroids; regular matroids; the polygon matroids of planar graphs; those matroids for which every connected component is either graphic or cographic; and those matroids for which every connected component is either binary or can be obtained from a binary matroid by a single circuit-hyperplane relaxation. We give an excluded-minor characterisation of the penultimate class, and show that the last of these classes has infinitely many excluded minors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 34, Issue 3, April 2005, Pages 616-633
نویسندگان
,