Abstract
A path separator of a graph G is a set of paths P={P1,…,Pt} such that for every pair of edges e,f∈E(G), there exist paths Pe,Pf∈P such that e∈E(Pe), f∉E(Pe), e∉E(Pf) and f∈E(Pf). The path separation number of G, denoted psn(G), is the smallest number of paths in a path separator. We shall estimate the path separation number of several graph families–including complete graphs, random graph, the hypercube–and discuss general graphs as well.
Original language | English (US) |
---|---|
Pages (from-to) | 26-33 |
Number of pages | 8 |
Journal | Discrete Applied Mathematics |
Volume | 213 |
DOIs | |
State | Published - Nov 20 2016 |
Keywords
- Network reliability
- Path covering
- Path decomposition
- Path separation
- Test sets
- Trees
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics