On Separating Path and Tree Systems in Graphs
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct elements in $X$, there exists a set in the separating system that contains exactly one of the two elements. A separating system of the vertex set of a graph $G$ is called a vertex-separating path (tree) system of $G$ if the elements of the separating system are paths (trees) in the graph $G$. In this paper, we focus on the size of the smallest vertex-separating path (tree) system for different types of graphs, including trees, grids, and maximal outerplanar graphs. Comment: 23 page, 3 figures dmtcs final version
Authors
- Prosenjit Bose (ORCID: https://orcid.org/0000-0002-8906-0573)
- Ahmad Biniaz (ORCID: https://orcid.org/0000-0002-6396-4494)
- Babak Miraftab (ORCID: https://orcid.org/0000-0001-8232-2502)
- Jean-Lou De Carufel (ORCID: https://orcid.org/0000-0002-6734-8234)
- Shakhar Smorodinsky (ORCID: https://orcid.org/0000-0003-3038-6955)
- Yelena Yuditsky (ORCID: https://orcid.org/0000-0002-6467-3437)
- Saeed Odak
- Anil Maheshwari (ORCID: https://orcid.org/0000-0002-1274-4598)
- Michiel Smid
Publication Details
- Journal
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2025-05-20
- DOI
- https://doi.org/10.46298/dmtcs.12743
- Citations
- 1
- Primary Topic
- Data Management and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 1.49
Funders
- National Science Foundation
- Fonds De La Recherche Scientifique - FNRS
- Natural Sciences and Engineering Research Council of Canada