On the number of edges in a graph with many two-hop disjoint paths

DOI10.1016/J.DAM.2020.01.003MaRDI QIDQ2192123zbMATH OpenOpenAlexWikidataFDO

Authors K. Takayama, Yusuke Kobayashi

Publication date 29 June 2020

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

Full work available at URL https://doi.org/10.1016/j.dam.2020.01.003

zbMATH Keywords

diameterconnectivitydisjoint paths2-hop path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Enumeration in graph theory (05C30) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• On the minimum number of edges of two-connected graphs with given diameter
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Trade-offs among degree, diameter, and number of paths
• Integer programming formulations for thek-edge-connected 3-hop-constrained network design problem
• scientific article; zbMATH DE number 3333196

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 795223 (Why is no real title available?)
• Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
• Identifying large robust network clusters via new compact formulations of maximum k-club problems
• On Critical Graphs of Diameter 2
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks
• Robustness and strong attack tolerance of low-diameter networks
• The k edge-disjoint 3-hop-constrained paths polytope
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra

Cited in

(5)

• On the number of edges of separated multigraphs
• Trade-offs among degree, diameter, and number of paths
• Paths containing two adjacent edges in \((2k+1)\)-edge-connected graphs
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Two paths joining given vertices in \(2k\)-edge-connected graphs

This page was built for publication: On the number of edges in a graph with many two-hop disjoint paths

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