عدد احاطه‌ای یالی 2-رنگین کمان و عدد پوچساز در درخت‌ها

فرض کنید g=(v,e) گرافی ساده با مجموعه رئوس v و مجموعه یال‌های e باشد. تابع f:e(g)→ƥ({1,2}) یک تابع احاطه‌گر یالی 2-رنگین کمان (e2rdf) برای گراف g نامیده می‌شود، هرگاه برای هر یال e با شرط f(e)=∅ داشته باشیم ⋃_(e^'∈n(e))〖f(e^' )={1,2}〗 که n(e) همسایگی باز یال e می‌باشد. وزن یک e2rdf برابر است با ω(f)=∑_(e∈e(g))〖|f(e)|〗. عدد احاطه‌ای یالی 2-رنگین کمان g را که با نماد γ_er2 (g) نمایش می‌دهیم، کمترین وزن یک e2rdf در گراف g است. فرض کنید s دنباله‌ای از درجات رئوس گراف g باشد که به صورت صعودی مرتب شدهاند. عدد پوچساز a(g) برابر با ماکسیمم مقدار عدد صحیح k است به طوری که حاصل جمع k جمله اول از دنباله s از تعداد یال‌های گراف g بیشتر نباشد. در حالت کلی این دو پارامتر قابل مقایسه نیستند. در این مقاله رابطه بین عدد احاطه‌ای یالی 2-رنگین کمان و عدد پوچساز در درخت‌ها را بررسی کرده و نشان می‌دهیم برای هر درخت t از مرتبه n≥2، .γ_er2 (t)≤a(t)