Vertex-separating path systems in random graphs

A set \(V\) is said to be separated by subsets \(V_1,\ldots,V_k\) if, for every pair of distinct elements of \(V\), there is a set \(V_i\) that contains exactly one of them. Imposing structural constraints on the separating subsets is often necessary for practical purposes and leads to a number of f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-08
Main Authors: Lichev, Lyuben, Sanhueza-Matamala, Nicolás
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Graphs
Optimization
Vertex sets
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set \(V\) is said to be separated by subsets \(V_1,\ldots,V_k\) if, for every pair of distinct elements of \(V\), there is a set \(V_i\) that contains exactly one of them. Imposing structural constraints on the separating subsets is often necessary for practical purposes and leads to a number of fascinating (and, in some cases, already classical) graph-theoretic problems. In this work, we are interested in separating the vertices of a random graph by path-connected vertex sets \(V_1,\ldots,V_k\), jointly forming a separating system. First, we determine the size of the smallest separating system of \(G(n,p)\) when \(np\to \infty\) up to lower order terms, and exhibit a threshold phenomenon around the sharp threshold for connectivity. Second, we show that random regular graphs of sufficiently high degree can typically be optimally separated by \(\lceil \log_2 n\rceil\) sets. Moreover, we provide bounds for the minimum degree threshold for optimal separation of general graphs.
ISSN:2331-8422