Separating path systems

DOI10.4310/JOC.2014.V5.N3.A4MaRDI QIDQ482277zbMATH OpenOpenAlexFDO

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) Vertex degrees (05C07) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

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

(12)

• On the path separation number of graphs
• scientific article; zbMATH DE number 4144025 (Why is no real title available?)
• Path separation by short cycles
• Separating path systems for the complete graph
• Separating path systems of almost linear size
• Separating path systems in trees
• On separating path and tree systems in graphs
• Separating the edges of a graph by cycles and by subdivisions of K₄
• Separating path systems in complete graphs
• Vertex-separating path systems in random graphs
• Separations of sets
• Separating systems and oriented graphs of diameter two

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)