کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647446 | 1342352 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Forbidden subgraphs generating a finite set
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
For a set F of connected graphs, a graph G is said to be F-free if G does not contain any member of F as an induced subgraph. The members of F are referred to as forbidden subgraphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow the possibility of the existence of exceptional graphs as long as their number is finite. However, in this type of research, if the set of k-connectedF-free graphs itself, denoted by Gk(F), is finite, then every graph in Gk(F) logically satisfies all the graph properties, except for possibly a finite number of exceptions. If this occurs, F does not give any information about a particular property. We think that such sets F obscure the view in the study of forbidden subgraphs, and we want to remove them. With this motivation, we study the sets F with finite Gk(F). We prove that if |F|â¤2 and Gk(F) is finite, then either K1,2âF or F consists of a complete graph and a star. For each of the values of k, 1â¤kâ¤6, we then characterize all the pairs {Kl,K1,m} such that Gk({Kl,K1,m}) is finite. We also give a complete characterization of F with |F|â¤3 and finite G2(F).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 19, 6 October 2013, Pages 1835-1842
Journal: Discrete Mathematics - Volume 313, Issue 19, 6 October 2013, Pages 1835-1842
نویسندگان
Jun Fujisawa, Michael D. Plummer, Akira Saito,