On the hardness of finding the geodetic number of a subcubic graph

DOI10.1016/j.ipl.2018.02.012zbMath1476.05041OpenAlexW2791124391MaRDI QIDQ1708262

Lucia Draque Penso, Victor R. Ramos, Letícia R. Bueno, Fábio Protti, Uéverton S. Souza, Dieter Rautenbach

Publication date: 5 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.02.012

zbMATH Keywords

computational complexitygeodetic numbergeodetic setgeodetic convexitymaximum degree three

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Parameterized Complexity of Geodetic Set ⋮ Well-partitioned chordal graphs ⋮ A general framework for path convexities ⋮ Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Target set selection with maximum activation time ⋮ Three problems on well-partitioned chordal graphs ⋮ Unnamed Item ⋮ Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes ⋮ Strong geodetic cores and Cartesian product graphs ⋮ Strong geodetic problem on complete multipartite graphs ⋮ Parameterized Complexity of Geodetic Set

Cites Work

• Hull number: \(P_5\)-free graphs and reduction rules
• Some remarks on the geodetic number of a graph
• On the geodetic and geodetic domination numbers of a graph
• On the geodetic number and related metric sets in Cartesian product graphs
• The hull and geodetic numbers of orientations of graphs
• The upper connected geodetic number and forcing connected geodetic number of a graph
• Some APX-completeness results for cubic graphs
• The geodetic hull number is hard for chordal graphs
• On the geodetic hull number of \(P_{k}\)-free graphs
• On The Edge Geodetic Number Of A Graph
• Computational Complexity of Geodetic Set

This page was built for publication: On the hardness of finding the geodetic number of a subcubic graph