کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903525 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounds on Directed star arboricity in some digraph classes
ترجمه فارسی عنوان
در برخی از کلاسهای گرافیگی بر روی ستاره ای متمرکز شده است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A galaxy is a forest of directed stars. The notion of galaxy can be related to Facility Location problems as well as wavelength assignment problems in optical networks. Amini et al. [Combinatorics, Probability & Computing, 19(2):161-182, 2010.] and Gonçalves et al. [Discrete Applied Mathematics, 160(6):744-754, 2012.] gave bounds on the minimum number of galaxies needed to cover the arcs of a digraph D, called directed star arboricity (dst(D)). They conjectured that those bounds could be improved such that dst(D)≤Δ(D), for Δ(D)≥3 and dst(D)≤2Δ+(D) for Δ+(D)≥2. In this work, we study the directed star arboricity in two non-trivial digraph classes: k-degenerate digraphs and tournaments.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 267-272
نویسندگان
, , , ,