tailieunhanh - Báo cáo toán học: "Nowhere-zero 3-flows in squares of graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Nowhere-zero 3-flows in squares of graphs | Nowhere-zero 3-flows in squares of graphs Rui Xu and Cun-Quan Zhang Department of Mathematics West Virginia University West Virginia USA xu@ cqzhang@ Submitted May 31 2002 Accepted Jan 15 2003 Published Jan 22 2003 MR Subject Classifications 05C15 05C20 05C70 05C75 90B10 Abstract It was conjectured by Tutte that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper we give a complete characterization of graphs whose squares admit nowhere-zero 3-flows and thus confirm Tutte s 3-flow conjecture for the family of squares of graphs. 1 Introduction All graphs considered in this paper are simple. Let G V E be a graph with vertex set V and edge set E. For any v E V G we use dG v Ng v to denote the degree and the neighbor set of v in G respectively. The minimal degree of a vertex of G is denoted by J G . We use Km for a complete graph on m vertices Pt for a path of length t and W4 for a graph obtained from a 4-circuit by adding a new vertex x and edges joining x to all the vertices on the circuit. We call x the center of this W4 and each edge with x as one end is called a center edge. Let D be an orientation of G. Then the set of all edges with tails or heads at a vertex v is denoted by E v or E- v . If an edge uv is oriented from u to v under D then we say D uv u v. The square of G denoted by G2 is the graph obtained from G by adding all the edges that join distance 2 vertices in G. We refer the reader to 1 for terminology not defined in this paper. Definition Let D be an orientation of G and f be a function E G Z. Then 1 . The ordered pair D f is called a k-flow of G if k 1 f e k 1 for every edge e E E G and pe E v f e EeeE- v f e for every v E V G . 2 . The ordered pair D f is called a Modular k-flow of G if for every v E V G PeEE v f e PeEE- v f e mod k . Partially supported by the National Security Agency under Grant MDA904-01-1-0022. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R5 1 The support of a k-flow Modular .