The Geodetic Hull Number is Hard for Chordal Graphs

2017/03/28 by Stéphane Bessy, Bessy, Stéphane, Mitre C. Dourado +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1704.02242

openalex publication_date 2017/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show the hardness of the geodetic hull number for chordal graphs.

Related

• Hull and Geodetic Numbers for Some Classes of Oriented Graphs
• Orientable convexity, geodetic and hull numbers in graphs
• Algorithms and complexity for geodetic sets on planar and chordal graphs
• On the geodetic and the hull numbers in strong product graphs
• Parameterized Complexity of Geodetic Set