On the path separation number of graphs

2013/12/05 by Balogh, József, Csaba, Béla, Martin, Ryan R. +1 · 2 citations
#05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.1724

Abstract

A path separator of a graph G is a set of paths P=\P₁,…,P_t\ such that for every pair of edges e,f∈ E(G), there exist paths P_e,P_f\inP such that e∈ E(P_e), f\not∈ E(P_e), e\not∈ E(P_f) and f∈ E(P_f). The path separation number of G, denoted \rm 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.

Cited by

• Separating path systems for cubic graphs and for complete bipartite graphs
• Separating edges by linearly many subdivisions

Related

• Separating path systems
• Separating paths systems of almost linear size
• Separating Path Systems for the Complete Graph
• Separating path systems for cubic graphs and for complete bipartite graphs
• Separating path systems in trees