کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423470 | 1342378 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weights of induced subgraphs in K1,r-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let H be a subgraph of a given graph G. The weight w(H) is defined to be the degree sum of the vertices of H in G. Investigations of this parameter are initiated by the result of Kotzig in 1955 who proved that every 3-connected planar graph contains an edge of weight at most 13.In this paper, we seek a bound f depending on some parameters of G and H such that w(Hâ²)â¤f for every induced subgraph Hâ² in G isomorphic to H. We obtain the following result for râ¥3: If H is an induced k-colorable subgraph of a K1,r-free graph G, and Iâ is a largest independent set in G, then w(H)â¤k(râ1)(nâα(G))ââvâV(H)âIâ((kâ1)(râ1)âdH(v)).Moreover, we give some sharpness examples.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 16, 28 August 2012, Pages 2429-2432
Journal: Discrete Mathematics - Volume 312, Issue 16, 28 August 2012, Pages 2429-2432
نویسندگان
Anja Pruchnewski, Margit Voigt,