TY - JOUR

T1 - On the path separation number of graphs

AU - Balogh, József

AU - Csaba, Béla

AU - Martin, Ryan R.

AU - Pluhár, András

N1 - Funding Information:
We appreciate the hard work of referees who uncovered some errors in the original manuscript. The first author’s research is partially supported by NSF CAREER Grant DMS-0745185 , TÁMOP-4.2.1/B-09/1/KONV-2010-0005 , and Marie Curie FP7-PEOPLE-2012-IIF 327763 . The second and fourth authors were partially supported by the European Union and the European Social Fund through project FuturICT.hu (Grant No.: TAMOP-4.2.2.C-11/1/KONV-2012-0013 ). The second author was also supported in part by the ERC-AdG . 321104 . The third author’s research partially was supported by NSF grant DMS-0901008 and by NSA grant H98230-13-1-0226 .
Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2016/11/20

Y1 - 2016/11/20

N2 - 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.

AB - 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.

KW - Network reliability

KW - Path covering

KW - Path decomposition

KW - Path separation

KW - Test sets

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=84995528724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84995528724&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.05.022

DO - 10.1016/j.dam.2016.05.022

M3 - Article

AN - SCOPUS:84995528724

VL - 213

SP - 26

EP - 33

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -