کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421127 684142 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Proximity, remoteness and minimum degree
ترجمه فارسی عنوان
نزدیکی، دور بودن و حداقل درجه
کلمات کلیدی
فاصله، نزدیکی، دورافتاده، حداقل درجه، انتقال، کل فاصله
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The average distance σ¯(v) of a vertex vv of a connected graph GG is the average of the distances between vv and all other vertices. The remoteness ρ(G)ρ(G) and proximity π(G)π(G) of GG are defined as maxv∈V(G)σ¯(v) and minv∈V(G)σ¯(v), respectively. Zelinka (1968) and, independently, Aouchiche and Hansen (2011) showed that the proximity and remoteness of a connected graph of order nn are bounded by approximately n4 and n2, respectively, and that the difference between the remoteness and proximity is bounded by approximately n4. We show that for graphs of minimum degree δδ, where δ≥2δ≥2, all three bounds can be improved by a factor of about 3δ+1. Our bounds are sharp except for an additive constant.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 223–228
نویسندگان
,