Premium
On a property of cyclic covers of p ‐graphs
Author(s) -
Politof Themistocles
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180107
Subject(s) - combinatorics , mathematics , path (computing) , graph , cover (algebra) , discrete mathematics , computer science , mechanical engineering , engineering , programming language
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.