Separating path systems

DOI10.4310/JOC.2014.V5.N3.A4zbMATH Open1305.05108arXiv1311.5051OpenAlexW2963185277MaRDI QIDQ482277FDOQ482277

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)

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.

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

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

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)

Cited In (6)

• Separating path systems for the complete graph
• Separating path systems of almost linear size
• Separating systems and oriented graphs of diameter two
• Path separation by short cycles
• On the path separation number of graphs
• Title not available (Why is that?)

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)