On the path separation number of graphs

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

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

Publication date 12 September 2016

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

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)

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.

Recommendations

• Separating path systems
• Path Separability of Graphs
• scientific article; zbMATH DE number 638688
• Path separation by short cycles
• scientific article; zbMATH DE number 861319

Cites work

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3584645 (Why is no real title available?)
• scientific article; zbMATH DE number 3253072 (Why is no real title available?)
• Clutter percolation and random graphs
• Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
• Extremal combinatorics. With applications in computer science
• Hamiltonian circuits in random graphs
• Identifying codes in line graphs
• Identifying path covers in graphs
• On a problem concerning separating systems of a finite set
• On separating systems
• Perfect matchings extend to Hamilton cycles in hypercubes
• Random graphs.
• Separating path systems

Cited in

(13)

• The vertex separation number of a graph equals its path-width
• Pagenumber of pathwidth-\(k\) graphs and strong pathwidth-\(k\) graphs
• Path Separability of Graphs
• scientific article; zbMATH DE number 1868869 (Why is no real title available?)
• scientific article; zbMATH DE number 2152547 (Why is no real title available?)
• Separating path systems of almost linear size
• Metric decompositions of path-separable graphs
• On computing the path number of a graph
• The separator theorem for rooted directed vertex graphs
• Separating path systems for the complete graph
• On the separation number of a graph
• On the number of edges of separated multigraphs
• Separating path systems

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)