کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1708927 1012836 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graphs with maximum size and lower bounded girth
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
Graphs with maximum size and lower bounded girth
چکیده انگلیسی

For integers n≥4n≥4 and ν≥n+1ν≥n+1, let ex(ν;{C3,…,Cn})ex(ν;{C3,…,Cn}) denote the maximum number of edges in a graph of order νν and girth at least n+1n+1. The {C3,…,Cn}{C3,…,Cn}-free graphs with order νν and size ex(ν;{C3,…,Cn})ex(ν;{C3,…,Cn}) are called extremal graphs and denoted by EX(ν;{C3,…,Cn})EX(ν;{C3,…,Cn}). We prove that given an integer k≥0k≥0, for each n≥2log2(k+2)n≥2log2(k+2) there exist extremal graphs with νν vertices, ν+kν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)(r;g)-cages are the exclusive elements in EX(ν0(r,g);{C3,…,Cg−1})EX(ν0(r,g);{C3,…,Cg−1}).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 25, Issue 3, March 2012, Pages 575–579
نویسندگان
, ,