Trade-offs among degree, diameter, and number of paths

DOI10.1016/j.dam.2022.12.007zbMath1506.05049OpenAlexW4311711421MaRDI QIDQ2112655

Akitoshi Kawamura, Kazuhisa Makino, Yusuke Kobayashi, Toshimasa Ishii

Publication date: 11 January 2023

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

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

zbMATH Keywords

connectivitydegree-diameter problemtight bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Distance in graphs (05C12) Connectivity (05C40) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• The \(k\) edge-disjoint 3-hop-constrained paths polytope
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On the number of edges in a graph with many two-hop disjoint paths
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• Asymptotically large (\(\Delta,D\))-graphs
• Connectivity of Regular Directed Graphs with Small Diameters
• On Moore Graphs with Diameters 2 and 3
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
• Connectivity of Imase and Itoh digraphs
• Two node-disjoint hop-constrained survivable network design and polyhedra
• Two Edge-Disjoint Hop-Constrained Paths and Polyhedra
• Robustness and Strong Attack Tolerance of Low-Diameter Networks
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs