On the geodetic hull number of \(P_{k}\)-free graphs

DOI10.1016/j.tcs.2016.05.047zbMath1345.05017OpenAlexW2412823324MaRDI QIDQ2629231

Dieter Rautenbach, Mitre C. Dourado, Lucia Draque Penso

Publication date: 5 July 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.047

zbMATH Keywords

geodetic numberinterval number\(P_k\)-free graphshull numbergeodetic convexity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (17)

A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ \(P_3\)-hull number of graphs with diameter two ⋮ Parameterized Complexity of Geodetic Set ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ The geodetic hull number is hard for chordal graphs ⋮ On the \(P_3\)-hull number of Hamming graphs ⋮ The Geodetic Hull Number is Hard for Chordal Graphs ⋮ Computing the hull number in \(\Delta \)-convexity ⋮ On the hardness of finding the geodetic number of a subcubic graph ⋮ On the geodetic number of complementary prisms ⋮ Convex and isometric domination of (weak) dominating pair graphs ⋮ On the parameterized complexity of the geodesic hull number ⋮ Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs ⋮ The hull number in the convexity of induced paths of order \(3\) ⋮ Delta invariant for Eulerian digraphs

Cites Work

• Unnamed Item
• Hull number: \(P_5\)-free graphs and reduction rules
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Some remarks on the geodetic number of a graph
• Complexity results related to monophonic convexity
• Triangle path transit functions, betweenness and pseudo-modular graphs
• On the computation of the hull number of a graph
• The hull number of a graph
• Convex sets in graphs. II: Minimal path convexity
• On triangle path convexity in graphs
• The geodetic number of a graph
• On the structure of graphs with few \(P_4\)s
• On the hull number of some graph classes
• The All-Paths Transit Function of a Graph
• Computing Minimum Geodetic Sets of Proper Interval Graphs
• Block decomposition approach to compute a minimum geodetic set
• On the Hull Number of Triangle-Free Graphs
• Convexity in Graphs and Hypergraphs
• Convexity and HHD-Free Graphs
• Convexity in Partial Cubes: The Hull Number
• Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs

This page was built for publication: On the geodetic hull number of \(P_{k}\)-free graphs