Separating path systems for the complete graph

DOI10.1016/J.DISC.2023.113784MaRDI QIDQ6136668zbMATHOpenAlexFDO

Authors Belinda Wickes

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

separating path systemsseparating systems for graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For any graph $G$, a separating path system of $G$ is a family of paths in $G$ with the property that for any edges $e,e^{\prime }inE(G)$ there is at least one path in the family that contains one of $e$ and $e^{\prime }$ but not the other. We investigate the size of the smallest separating path system for $K_n$, denoted $f(K_n)$. It is known that $n-1leqf(K_n)leq2n+4$, our main result is a construction that reduces the upper bound to $f(K_n)leqleft(frac2116+o(1)ight)n$ for sufficiently large $n$, and to $f(K_n)leqn$ whenever $n=p,p+1$ for prime $p$. A key idea in our construction is to reduce the problem to finding a single path with some particular properties we call a Generator Path. These are defined in such a way that the $n$ cyclic rotations of a generator path provide a separating path system for $K_n$. Hence existence of a generator path for some $K_n$ gives $f(K_n)leqn$. We construct such paths for all $K_n$ with $nleq20$, and show that generator paths exist whenever $n$ is prime.

Recommendations

• Separating path systems
• Separating path systems of almost linear size
• On the path separation number of graphs
• Path separation by short cycles

Cites work

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• Identifying path covers in graphs
• On separating systems of graphs
• On the path separation number of graphs
• Paths through equally spaced points on a circle
• Separating path systems
• Separating systems and oriented graphs of diameter two

Cited in

(1)

• Separating path systems of almost linear size

This page was built for publication: Separating path systems for the complete graph

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