On Separating Path and Tree Systems in Graphs

2023/12/21 by Biniaz, Ahmad, Bose, Prosenjit, De Carufel, Jean-Lou +6
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2312.14295

Abstract

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.

Related

• Separating path systems
• Separating path systems in trees
• Separating paths systems of almost linear size
• Separating Path Systems for the Complete Graph
• Separating the edges of a graph by cycles and by subdivisions of K₄