On the path separation number of graphs

DOI10.1016/J.DAM.2016.05.022zbMATH Open1344.05078arXiv1312.1724OpenAlexW2964084646MaRDI QIDQ313786FDOQ313786

Béla Csaba, Ryan R. Martin, József Balogh, András Pluhár

Publication date: 12 September 2016

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

Abstract: A path separator of a graph $G$ is a set of paths $mathcalP=P_1,ldots,P_t$ such that for every pair of edges $e,finE(G)$, there exist paths $P_e,P_{f}inmathcalP$ such that $einE(P_e)$, $fotinE(P_e)$, $eotinE(P_f)$ and $finE(P_f)$. The path separation number of $G$, denoted $mpsn(G)$, is the smallest number of paths in a path separator. We shall estimate the path separation number of several graph families, including complete graphs, random graph, the hypercube, and discuss general graphs as well.

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

zbMATH Keywords

treesnetwork reliabilitypath coveringpath decompositionpath separationtest sets

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• Identifying Codes in Line Graphs
• Hamiltonian circuits in random graphs
• Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
• Perfect matchings extend to Hamilton cycles in hypercubes
• Extremal Combinatorics
• Clutter percolation and random graphs
• Identifying path covers in graphs
• Separating path systems
• On a problem concerning separating systems of a finite set
• On separating systems

Cited In (11)

• Separating path systems for the complete graph
• Pagenumber of pathwidth-\(k\) graphs and strong pathwidth-\(k\) graphs
• Separating path systems of almost linear size
• Title not available (Why is that?)
• The vertex separation number of a graph equals its path-width
• Metric decompositions of path-separable graphs
• The separator theorem for rooted directed vertex graphs
• Path Separability of Graphs
• Title not available (Why is that?)
• On computing the path number of a graph
• On the number of edges of separated multigraphs

This page was built for publication: On the path separation number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313786)