Cycle structure of edge labelled graphs

AbstractIn this paper we examine the cyclic structure of graphs with edges labelled by elements of a partial order under the operation of deleting any edge whose label is less than or equal to all labels of edges of some cycle containing that edge. We show that all graphs obtained after repeating the above operation as many times as possible have similar structure with respect to the number of edges remaining and thus, in particular, the presence or absence of cycles. To show this, we apply some results of matroid theory. We also give an efficient algorithm to determine whether or not the resulting graph is acyclic. As an application to relational database theory, we show how this algorithm can be combined with a new characterization of database acyclicity to determine the cyclicity of a relational database scheme