For a graph G, an edge-separating (resp. vertex-separating) path system of G is a family of paths in G such that for any pair of edges <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$e_1, e_2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>e</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>e</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> (resp. pair of vertices <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$v_1, v_2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>v</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>) of G there is at least one path in the family that contains one of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$e_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$e_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> (resp. <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$v_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$v_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>) but not the other. We determine the size of a minimum edge-separating path system of an arbitrary tree T as a function of its number of leaves and degree-two vertices. We obtain bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. We obtain similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously. Finally, we investigate the size of a minimal vertex-separating path system in Erdős–Rényi random graphs.

Separating path systems in trees

期刊论文
发表日期：

2025年12月27日

查看全文

Francisco Arrepol,
Patricio Asenjo,
Raúl Astete,
Victor Cartes,
Anahí Gajardo,
Valeria Henríquez,
Catalina Opazo,
Nicolás Sanhueza-Matamala,
Christopher Thraves Caro

摘要

For a graph G, an edge-separating (resp. vertex-separating) path system of G is a family of paths in G such that for any pair of edges $e_1, e_2$ $e_{1}, e_{2}$ (resp. pair of vertices $v_1, v_2$ $v_{1}, v_{2}$ ) of G there is at least one path in the family that contains one of $e_1$ $e_{1}$ and $e_2$ $e_{2}$ (resp. $v_1$ $v_{1}$ and $v_2$ $v_{2}$ ) but not the other. We determine the size of a minimum edge-separating path system of an arbitrary tree T as a function of its number of leaves and degree-two vertices. We obtain bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. We obtain similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously. Finally, we investigate the size of a minimal vertex-separating path system in Erdős–Rényi random graphs.