CYCLE STRUCTURE OF EDGE LABELED GRAPHS

In this paper we examine the cyclic structure of graphs with edges lab elled by elements of a partial order under the operation of deleting a ny edge whose label is less than or equal to all labels of edges of so me cycle containing that edge. We show that all graphs obtained after repeating the above operation as many times as possible have similar s tructure with respect to the number of edges remaining and thus, in pa rticular, the presence or absence of cycles. To show this, we apply so me results of matroid theory. We also give an efficient algorithm to d etermine whether or not the resulting graph is acyclic. As an applicat ion to relational database theory, we show however is algorithm can be combined with a new characterization of database acyclicity to determ ine the cyclicity of a relational database scheme.