کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656995 1343706 2011 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Circular flow on signed graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Circular flow on signed graphs
چکیده انگلیسی

The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 101, Issue 6, November 2011, Pages 464-479