On the geodetic hull number of P_k-free graphs

DOI10.1016/J.TCS.2016.05.047MaRDI QIDQ2629231zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, Dieter Rautenbach, 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

\(P_k\)-free graphsgeodetic convexitygeodetic numberhull numberinterval number

Mathematics Subject Classification ID

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

Recommendations

• Geodetic convexity parameters for graphs with few short induced paths
• Hull number: \(P_5\)-free graphs and reduction rules
• On the hull number of some graph classes
• The geodetic hull number is hard for chordal graphs
• Geodetic number versus hull number in P₃-convexity

Cites work

• Block decomposition approach to compute a minimum geodetic set
• Complexity results related to monophonic convexity
• Computing minimum geodetic sets of proper interval graphs
• Convex sets in graphs. II: Minimal path convexity
• Convexity and HHD-Free Graphs
• Convexity in Graphs and Hypergraphs
• Convexity in partial cubes: the hull number
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hull number: \(P_5\)-free graphs and reduction rules
• On the computation of the hull number of a graph
• On the hull number of some graph classes
• On the hull number of triangle-free graphs
• On the structure of graphs with few P₄s
• On triangle path convexity in graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Some remarks on the geodetic number of a graph
• The All-Paths Transit Function of a Graph
• The geodetic number of a graph
• The hull number of a graph
• Triangle path transit functions, betweenness and pseudo-modular graphs

Cited in

(23)

• On the \(P_3\)-hull number of some products of graphs
• 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 Steiner, geodetic and hull numbers of graphs
• 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
• \(P_3\)-hull number of graphs with diameter two
• On the -interval and the -convexity numbers of graphs and graph products
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• On the P₃-hull number of Hamming graphs
• Computing the hull number in -convexity
• On the parameterized complexity of the geodesic hull number
• The geodetic hull number is hard for chordal graphs
• Hull number: \(P_5\)-free graphs and reduction rules
• Geodetic convexity parameters for graphs with few short induced paths
• The geodetic hull number is hard for chordal graphs
• A polynomial time algorithm for geodetic hull number for complementary prisms
• Parameterized complexity of geodetic set
• Improved bounds for geodetic hulls
• Carathéodory number and exchange number in -convexity
• Helly number, Radon number and rank in -convexity on graphs

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

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