Separating path systems for the complete graph

DOI10.1016/J.DISC.2023.113784zbMATH Open1530.05157arXiv2209.04302OpenAlexW4388687315MaRDI QIDQ6136668FDOQ6136668

Authors: Belinda Wickes 

Publication date: 17 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

Recommendations

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

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)

Cites Work

• On the path separation number of graphs
• Title not available (Why is that?)
• Identifying path covers in graphs
• Separating path systems
• Separating systems and oriented graphs of diameter two
• On separating systems of graphs
• Paths through equally spaced points on a circle

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)