Ahmad Biniaz ; Prosenjit Bose ; Jean-Lou De Carufel ; Anil Maheshwari ; Babak Miraftab et al. - On Separating Path and Tree Systems in Graphs

dmtcs:12743 - Discrete Mathematics & Theoretical Computer Science, May 20, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.12743
On Separating Path and Tree Systems in GraphsArticle

Authors: Ahmad Biniaz ; Prosenjit Bose ; Jean-Lou De Carufel ; Anil Maheshwari ; Babak Miraftab ; Saeed Odak ; Michiel Smid ; Shakhar Smorodinsky ; Yelena Yuditsky

    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.


    Volume: vol. 27:2
    Section: Graph Theory
    Published on: May 20, 2025
    Accepted on: April 24, 2025
    Submitted on: December 25, 2023
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 178 times.
    This article's PDF has been downloaded 151 times.