On the path separation number of graphs

József Balogh, Béla Csaba, Ryan R. Martin, András Pluhár

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)26-33
Number of pages8
JournalDiscrete Applied Mathematics
StatePublished - Nov 20 2016


  • Network reliability
  • Path covering
  • Path decomposition
  • Path separation
  • Test sets
  • Trees

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the path separation number of graphs'. Together they form a unique fingerprint.

Cite this