On a property of cyclic covers of p- graphs
1988
A directed graph G with a source s and a sink t is called a p-graph if every edge of G belongs to an elementary (s,t)-path of G. If C is a cycle of the p-graph G then a cyclic cover of C is a set of (s,t)-paths of G that contains all the edges of C. A cyclic cover Q is minimal if for every path P e Q, Q = {P} is not a cover of C. The following property is known and was used in providing an important result in network reliability: A cyclic p-graph has a cycle C and a path P such that P is not contained in any minimal cover of C. In this note we give a simpler proof of this property which provides more insight into the nature of cyclic covers in p-graphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
3
References
1
Citations
NaN
KQI