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

DOI10.1016/J.IPL.2018.02.012zbMATH Open1476.05041OpenAlexW2791124391MaRDI QIDQ1708262FDOQ1708262

Authors: L. R. Bueno, Lucia Draque Penso, Fábio Protti, Victor R. Ramos, Dieter Rautenbach, Uéverton S. Souza 

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

Recommendations

• scientific article; zbMATH DE number 5531985
• Hardness and approximation for the geodetic set problem in some graph classes
• Some results on geodetic number of graphs
• scientific article; zbMATH DE number 1933222
• On pitfalls in computing the geodetic number of a graph
• The geodetic numbers of graphs and digraphs
• The geodetic numbers of graphs and digraphs
• On the geodetic number of a graph
• On the geodomatic number of a graph
• On the geodetic and geodetic domination numbers of a graph

zbMATH Keywords

computational complexitygeodetic setgeodetic convexitygeodetic numbermaximum degree three

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes
• Computational Complexity of Geodetic Set
• Strong geodetic cores and Cartesian product graphs
• Parameterized complexity of geodetic set
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• Some remarks on the geodetic number of a graph
• Well-partitioned chordal graphs
• Algorithms and complexity for geodetic sets on partial grids
• Three problems on well-partitioned chordal graphs
• Strong geodetic problem on complete multipartite graphs
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• Hardness and approximation for the geodetic set problem in some graph classes
• Title not available (Why is that?)
• On the computational complexity of the strong geodetic recognition problem
• Target set selection with maximum activation time
• Parameterized Complexity of Geodetic Set

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

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