Some remarks on the geodetic number of a graph

DOI10.1016/j.disc.2009.09.018zbMath1209.05129OpenAlexW2110486245MaRDI QIDQ965962

Mitre C. Dourado, Fábio Protti, Jayme Luiz Szwarcfiter, Dieter Rautenbach

Publication date: 27 April 2010

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

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00017414/IfM_Preprint_M_09_15.pdf

zbMATH Keywords

split graphconvex hullconvex setgeodetic numbercographunit interval graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items

Complexity aspects of the triangle path convexity ⋮ Parameterized Complexity of Geodetic Set ⋮ On the geodetic hull number of \(P_{k}\)-free graphs ⋮ Well-partitioned chordal graphs ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ On the toll number of a graph ⋮ The strong convexity spectra of grids ⋮ Strong edge geodetic problem in networks ⋮ The forcing total restrained geodetic number and the total restrained geodetic number of a graph: realizability and complexity ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ Total restrained geodetic number of graphs ⋮ On the geodetic and the hull numbers in strong product graphs ⋮ The convexity of induced paths of order three and applications: complexity aspects ⋮ Three problems on well-partitioned chordal graphs ⋮ Geodetic convexity and Kneser graphs ⋮ On the hardness of finding the geodetic number of a subcubic graph ⋮ Unnamed Item ⋮ On the contour of graphs ⋮ Towards a new framework for domination ⋮ On the geodetic number of complementary prisms ⋮ Inapproximability results for graph convexity parameters ⋮ Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes ⋮ On the contour of bipartite graphs ⋮ On the geodetic and geodetic domination numbers of a graph ⋮ Partitioning a graph into convex sets ⋮ Complexity results related to monophonic convexity ⋮ Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ Strong geodetic problem in networks ⋮ Strong geodetic cores and Cartesian product graphs ⋮ Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ Strong geodetic problem on complete multipartite graphs ⋮ Parameterized Complexity of Geodetic Set ⋮ Graphs with large total geodetic number ⋮ On the edge geodetic and edge geodetic domination numbers of a graph ⋮ An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs

Cites Work

• On geodetic sets formed by boundary vertices
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A short proof that `proper = unit'
• The geodetic number of a graph
• On the Steiner, geodetic and hull numbers of graphs
• On the geodetic number of a graph
• Dominating Sets in Chordal Graphs
• Graph Classes: A Survey
• Computational Complexity of Geodetic Set
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item