کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8941797 1645038 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Modulo orientations with bounded independence number
ترجمه فارسی عنوان
جهت گیری های مدول با تعداد محدود استقلال
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A mod (2p+1)-orientation D is an orientation of G such that dD+(v)≡dD−(v)(mod2p+1) for any vertex v∈V(G). Extending Tutte's integer flow conjectures, it was conjectured by Jaeger that every 4p-edge-connected graph has a mod (2p+1)-orientation. However, this conjecture has been disproved in Han et al. (2018) recently. Infinite families of 4p-edge-connected graphs (for p≥3) and (4p+1)-edge-connected graphs (for p≥5) with no mod (2p+1)-orientation are constructed in Han et al. (2018). In this paper, we show that every family of graphs with bounded independence number has only finitely many contraction obstacles for admitting mod (2p+1)-orientations, contrasting to those infinite families. More precisely, we prove that for any integer t≥2, there exists a finite family F=F(p,t) of graphs that do not have a mod (2p+1)-orientation, such that every graph G with independence number at most t either admits a mod (2p+1)-orientation or is contractible to a member in F. This indicates that the problem of determining whether every k-edge-connected graph with independence number at most t admits a mod (2p+1)-orientation is computationally solvable for fixed k and t. In particular, the graph family F(p,2) is determined, and our results imply that every 8-edge-connected graph G with independence number at most two admits a mod 5-orientation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 14-22
نویسندگان
, , ,