کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8900755 | 1631719 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An extremal problem on graphic sequences with a realization containing every â-tree on k vertices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An extremal problem on graphic sequences with a realization containing every â-tree on k vertices An extremal problem on graphic sequences with a realization containing every â-tree on k vertices](/preview/png/8900755.png)
چکیده انگلیسی
A graph G is a â-tree if G=Kâ+1, or G has a vertex v whose neighborhood is a clique of order â, and Gâv is a â-tree. A non-increasing sequence Ï=(d1,â¦,dn) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices. Yin and Li (2009) proved that if kâ¯â¥â¯2, nâ¥92k2+192k and Ï=(d1,â¦,dn) is a graphic sequence with âi=1ndi>(kâ2)n, then Ï has a realization containing every 1-tree (the usual tree) on k vertices. Moreover, the lower bound (kâ2)n is the best possible. This is a variation of a conjecture due to ErdÅs and Sós. Recently, Zeng and Yin (2016) investigated an analogue extremal problem for 2-trees and prove that if kâ¯â¥â¯3, nâ¥2k2âk and Ï=(d1,â¦,dn) is a graphic sequence with âi=1ndi>4kâ53n, then Ï has a realization containing every 2-tree on k vertices. Moreover, the lower bound 4kâ53n is almost the best possible. In this paper, we consider the most general case ââ¯â¥â¯3 and prove that if ââ¯â¥â¯3, kâ¥â+1,nâ¥2k2ââk+k and Ï=(d1,â¦,dn) is a graphic sequence with âi=1ndi>2âkâââ3â+1n, then Ï has a realization containing every â-tree on k vertices. We also show that the lower bound 2âkâââ3â+1n is almost the best possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 337, 15 November 2018, Pages 487-493
Journal: Applied Mathematics and Computation - Volume 337, 15 November 2018, Pages 487-493
نویسندگان
De-Yan Zeng, Jian-Hua Yin,