tailieunhanh - Báo cáo toán học: "Nowhere-zero k-flows of supergraphs"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Nowhere-zero k-flows of supergraphs. | Nowhere-zero k-flows of supergraphs Bojan Mohar and Riste Skrekovski Department of Mathematics University of Ljubljana Jadranska 19 1111 Ljubljana Slovenia Submitted March 28 2000 Accepted January 30 2001. Mathematical Subject Classification 05C15 05C99. Abstract Let G be a 2-edge-connected graph with o vertices of odd degree. It is well-known that one should and can add o edges to G in order to obtain a graph which admits a nowhere-zero 2-flow. We prove that one can add to G a set of L4 J r2 LoJ and r2 L7J edges such that the resulting graph admits a nowhere-zero 3-flow 4-flow and 5-flow respectively. 1 Introduction Graphs in this paper may contain multiple edges and loops. A vertex of G is odd even if its degree is odd even . We denote by o G the number of odd vertices of G. Let G be a graph such that no component of G is a cycle. Then there is a unique graph G which is homeomorphic to G and has no vertices of degree 2. We say that G is obtained from G by suppressing vertices of degree 2 and we denote this by G G. Let r be an Abelian group let D be an orientation of a graph G and f E G r. The pair D f is a r-flow in G if the following condition is satisfied at every vertex v 2 V G E f e 12 f e e2E y e2E- v Supported in part by the Ministry of Science and Technology of Slovenia Research Project J1-0502-0101-99. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R20 1 where E v and E- v denote the sets of outgoing and ingoing edges with respect to the orientation D incident with v respectively. A flow D f is nowhere-zero if f e 0 for every e 2 E G . If r z and k f e k then D f is a k-flow. The concept of nowhere-zero flows was introduced and studied by Tutte 9 . For a 2-edge-connected graph G and a group r of order k Tutte 8 proved that G admits a nowhere-zero k-flow if and only if it admits a nowhere-zero r-flow. Seymour 7 proved that every 2-edge-connected graph admits a nowhere-zero 6-flow. We refer to 10 for .