Separating path systems

DOI10.4310/JOC.2014.V5.N3.A4MaRDI QIDQ482277zbMATHOpenAlexFDO

Authors Victor Falgas-Ravry, Teeradej Kittipassorn, Dániel Korándi, Shoham Letzter, Bhargav P. Narayanan

Publication date 22 December 2014

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5051

zbMATH Keywords

minimal separating path system

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38)

Abstract: We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$-vertex graph admits a separating path system of size $O(n)$ and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.

Recommendations

• On the path separation number of graphs
• Path Separability of Graphs
• Path separation by short cycles
• On the path separability of planar graphs
• Separating systems and oriented graphs of diameter two

Cited in

(7)

• scientific article; zbMATH DE number 4144025 (Why is no real title available?)
• Separations of sets
• Path separation by short cycles
• Separating path systems of almost linear size
• Separating systems and oriented graphs of diameter two
• On the path separation number of graphs
• Separating path systems for the complete graph

This page was built for publication: Separating path systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482277)