کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651899 1632582 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Induced minors and well-quasi-ordering
ترجمه فارسی عنوان
افراد زیر سن قانونی و به خوبی شبه سفارش
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A graph H is an induced minor of a graph G if it can be obtained from an induced subgraph of G by contracting edges. Otherwise, G is said to be H-induced minor-free. Robin Thomas showed in [Graphs without K4and well-quasi-ordering, Journal of Combinatorial Theory, Series B, 38(3):240 – 247, 1985] that K4-induced minor-free graphs are well-quasi ordered by induced minors.We provide a dichotomy theorem for H-induced minor-free graphs and show that the class of H-induced minor-free graphs is well-quasi-ordered by the induced minor relation if and only if H is an induced minor of the gem (the path on 4 vertices plus a dominating vertex) or of the graph obtained by adding a vertex of degree 2 to the complete graph on 4 vertices.Similar dichotomy results were previously given by Guoli Ding in [Subgraphs and well-quasi-ordering, Journal of Graph Theory, 16(5):489–502, 1992] for subgraphs and Peter Damaschke in [Induced subgraphs and well-quasi-ordering, Journal of Graph Theory, 14(4):427–435, 1990] for induced subgraphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 197-201