کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8941797 | 1645038 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Modulo orientations with bounded independence number
ترجمه فارسی عنوان
جهت گیری های مدول با تعداد محدود استقلال
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 14-22
نویسندگان
Miaomiao Han, Hong-Jian Lai, Jiaao Li,