Geodetic Convexity Parameters for Graphs with Few Short Induced Paths
DOI10.1007/978-3-662-53536-3_3zbMath1417.05204OpenAlexW2527031230MaRDI QIDQ3181044
Mitre C. Dourado, Dieter Rautenbach, Lucia Draque Penso
Publication date: 22 December 2016
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-53536-3_3
Carathéodory numberconvexity numbergeodetic numberinterval number\(P_k\)-free graphshull numbergeodetic convexityRadon number\((q,q-4)\)-graphs
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Hull number: \(P_5\)-free graphs and reduction rules
- Near-linear-time algorithm for the geodetic Radon number of grids
- On the Carathéodory number of interval and graph convexities
- 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
- Some remarks on the convexity number of a graph
- The convexity number of a graph
- On the geodetic Radon number of grids
- On the convexity number of graphs
- 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
