Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Even Bonds of Prescribed Directed Parity. | Even Bonds of Prescribed Directed Parity Sven Hartmann and . Little Massey University Palmerston North New Zealand @ Submitted Aug 1 2005 Accepted Nov 8 2005 Published Nov 25 2005 Mathematics Subject Classification 05C75 Abstract Given a set S of vertices in a graph the cocycle determined by S is the set of edges joining a vertex in S to a vertex not in S. A bond is a minimal non-empty cocycle. We characterise graphs that admit an orientation under which every bond of even cardinality has a prescribed directed parity. 1 Introduction In 2 Fischer and Little characterised those graphs that admit an orientation under which every even circuit has directed parity in agreement with a preassigned parity. In other words they assign a parity to every circuit of even length and determine the conditions under which the graph can be oriented so that for every even circuit the parity of the number of edges directed in agreement with a specified sense is equal to the parity assigned to that circuit. In this paper we solve the corresponding problem for even bonds. Given a graph G let VG and EG denote its vertex set and its edge set respectively. An edge is called a link if it connects two distinct vertices and a loop otherwise. Two edges are parallel if they connect the same vertices. By G X we denote the subgraph of G induced by a subset X of either VG or EG. As long as no confusion arises we will write x instead of X if X consists of a single element x only. For any two subsets S and T of VG let S T denote the set of all edges in EG connecting some vertex in S to some vertex in T. In particular @S S VG S is called a cocycle of G. A cocycle B is said to be elementary or a bond if G has a component C such that B c EC and C B has just two components. That is deleting the edges of B from G increases the number of components of G by exactly 1. It is well known cf. 1 that a bond is just a minimal non-empty cocycle and that every cocycle is a sum .
